走出的回路一定在 scc 中，因此使用 tarjan 求出 scc。

复杂度困境

从每一个点都做一遍 bfs 会超时。

期望只从 scc 的一个点出发做 bfs，即可判断 scc 中的所有点。

破局：“以点代面”

发现如下性质。 从 scc 内的任意一点 $u$ 可以走出一条合法的回路 $\Leftrightarrow$ scc 内所有点都可以走出一条合法的回路。

充分性： 存在一条从 $u$ 回到 $u$ 的合法回路，回路长度 $L \bmod 3 = 1$。 从任意一个其他点 $v$ 可以首先走到这个回路上，设路径长度为 $l_1$；在这个回路上绕 $k$ 圈，路径长度为 $kL$；最后离开回路，回到点 $v$，设路径长度为 $l_2$。 从 $v$ 到 $v$ 的回路合法，等价于 $(l_1+l_2+kL) \bmod 3 = (l_1+l_2+k) \bmod 3 =1$。 可以发现，不管 $l_1 + l_2$ 在模 3 意义下为多少，都可以改变 $k$ 的值使等式成立。充分性得证。

必要性：由命题直接得到。

我们从每个 scc 的任意点做分层图 bfs，判断这个点是否可以走一条合法的回路。如果可以，则将答案加上当前 scc 的大小。

代码实现

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 2e5 + 10, M = 4e5 + 10;
struct Edge{
    int to, nxt;
}edge[M];
int n, m;
int head[N], tot;
int nowdfn, dfn[N], low[N], stk[N], tp; 
bool instk[N];
int color[N], nowscc; 
vector<int> scc[N];
bool vis[N][3];
void add(int u, int v){
    edge[++tot].to = v;
    edge[tot].nxt = head[u];
    head[u] = tot;
}
void tarjan(int u){
    dfn[u] = low[u] = ++nowdfn;
    stk[++tp] = u, instk[u] = 1;
    for(int i = head[u]; i; i = edge[i].nxt){
        int v = edge[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }else if(instk[v]){//ancestor
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(dfn[u] == low[u]){
        ++nowscc;
        int p = 0;
        do{
            p = stk[tp--];
            scc[nowscc].push_back(p);
            instk[p] = 0;
            color[p] = nowscc;
        }while(tp!=0 && p != u);
    }
}
void bfs(int st){
    queue<pii> q;
    q.push({st, 0});
    vis[st][0] = 1;
    while(!q.empty()){
        int u = q.front().first, r = q.front().second;
        q.pop();
        for(int i = head[u]; i; i = edge[i].nxt){
            int v = edge[i].to;
            if(!vis[v][(r+1)%3]){
                vis[v][(r+1)%3] = 1;
                q.push({v, (r+1)%3});
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1, u, v; i <= m; i ++){
        cin >> u >> v;
        add(u, v);
    }
    for(int i = 1; i <= n; i ++){
        if(!dfn[i]) tarjan(i);
    }
    int ans = 0;
    for(int i = 1; i <= nowscc; i ++){//scc
        bfs(scc[i][0]);
        if(vis[scc[i][0]][1]) ans += scc[i].size();
    }
    cout << ans;
    return 0;
}

2772. 环

简要题意

$n$ 个节点 $m$ 条边的有向图，求有多少个节点 $u$ 满足 存在一个包含 $u$ 在内的环，环长对 $3$ 取模时 $0$

$n\le200000,m\le400000$

思路

看到了 有向图、环、$n \le 200000$，就可以联想到强联通分量。

考虑对每一个强联通分量依次处理，很显然，不可能有一个环跨过强连通分量，所以这样不会少算可能性。

强连通分量的定义是：满足任意两个节点可以互相到达的极大子图。

所以一个强联通分量中，只要一个节点被以 $x$ 和 $x+1$ 两个计数器访问，那么这个节点就应该加入贡献。

然后这道题目就做完了，有什么疑问或写的不清晰的地方欢迎提出

最后放一份代码

#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr size_t N = 200005, M = 400005;
int n, m;
int head[N], nxt[M], to[M], cntg;
int dfn[N], low[N], sta[N], belong[N], cntd, top, scc;
bool vis[N][3];//vis[u][c]表示u是否被已c的计数器访问过
int res;
void addEdge(int u, int v)
{
    nxt[++cntg] = head[u];
    to[cntg] = v;
    head[u] = cntg;
}
void tarjan(int u)//强连通分量
{
    dfn[u] = low[u] = ++cntd;
    sta[++top] = u;
    for (int e = head[u]; e > 0; e = nxt[e])
    {
        int v = to[e];
        if (dfn[v] == 0)
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (belong[v] == 0)
        {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u])
    {
        int v;
        scc++;
        do
        {
            v = sta[top--];
            belong[v] = scc;
        } while (v != u);
    }
}
void dfs(int u, int c)
{
    if (vis[u][c]) return;
    vis[u][c] = true;
    for (int e = head[u]; e > 0; e = nxt[e])
    {
        int v = to[e];
        if (belong[u] == belong[v])//保证在同一个强连通分量中
        {
            dfs(v, (c == 2 ? 0 : c + 1));
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    int u, v;
    for (int i = 1; i <= m; i++)
    {
        cin >> u >> v;
        addEdge(u, v);
    }
    for (int i = 1; i <= n; i++)
    {
        if (dfn[i] == 0)
        {
            tarjan(i);
        }
        if (!vis[i][0] && !vis[i][1] && !vis[i][2])//这个节点的强连通分量没有被dfs过
        {
            dfs(i, 0);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if ((vis[i][0] && vis[i][1]) || (vis[i][1] && vis[i][2]) || (vis[i][2] && vis[i][0]))
        {
            //这个节点被以两个相差1的计数器访问了，答案+1
            res++;
        }
    }
    cout << res << '\n';
    return 0;
}