题目描述

难度分:$2100$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 4 \times 10^5$，$m$之和$\leq 4 \times 10^5$。

每组数据输入$n(1 \leq n \leq 4 \times 10^5)$，$m(0 \leq m \leq 4 \times 10^5)$表示一个$n$点$m$边的有向图。

然后输入$m$条边，每条边输入$v$，$w$，表示一条$v$到$w$的有向边。节点编号从$1$开始。保证图中无重边，但图中可能有自环。

对每个点$v$，考虑从$1$到$v$的路径个数：

• 没有：输出$0$。
• 只有一条：输出$1$。
• 不止一条，但个数有限：输出$2$。
• 有无数条路径：输出$-1$。

注：路径允许是空的，这意味着$1$到$1$也算一条路径（长度为$0$）。
注：路径允许有重复的点和边。

输入样例

5

6 7
1 4
1 3
3 4
4 5
2 1
5 5
5 6

1 0

3 3
1 2
2 3
3 1

5 0

4 4
1 2
2 3
1 4
4 3

输出样例

1 0 1 2 -1 -1 
1 
-1 -1 -1 
1 0 0 0 0 
1 1 2 1 

算法

$tarjan$缩点+拓扑排序

这个题的思路还是很容易想的，但是实现起来没那么容易。首先题面中就已经说明了给定的有向图是存在环的，而且可能是自环，这就引导我们先对整张图用$tarjan$算法缩点，将原图变为每个强连通分量构成的$DAG$。而原图中是存在自环的，我们可以把自环的节点$u$拆成$u$和$u+n$两个节点来做，这样一来，只要某个节点所在的强连通分量中超过$1$个节点，那这个强连通分量里就是有环的。

转化成了$DAG$就方便统计路径了，直接从$1$节点开始按照拓扑序来统计就好了。但是由于初始化队列的时候并不是把所有入度为$0$的连通分量都加入了队列，而是只加入了$1$节点所在的连通分量，所以如果入度为$0$的时候才加入下一个连通分量，就会导致有些本来应该访问到的点访问不到。因此，只要访问到了节点$u$，就要让它入队。经过测试，在本题的数据规模下，每个点入队的次数控制不超过$70$次就可以。

在这个过程中只要碰到了环，那么它后面所有节点的答案就都是$-1$，否则正常统计。

复杂度分析

时间复杂度

$tarjan$缩点需要遍历整个图的邻接表，时间复杂度是$O(n+m)$。之后对强连通分量建图需要遍历原图，时间复杂度也是$O(n+m)$。最后按照拓扑序统计答案，每个节点的入队次数不超过$70$，可以看成是一个较大的常数，时间复杂度仍然是$O(n+m)$。

综上，整个算法的时间复杂度为$O(n+m)$。

空间复杂度

$tarjan$缩点需要的辅助数组都是$O(n)$规模的，额外空间为$O(n)$。而原图和强连通分量新图的空间都是$O(n+m)$，因此瓶颈应该在这里，整个算法的额外空间复杂度为$O(n+m)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;

const int N = 800001;
int T, n, m, ts, scc_cnt;
int dfn[N], low[N], id[N], sz[N], dp[N];
bool in_stk[N];
vector<int> graph[N], ngraph[N];
stack<int> stk;

void init() {
    ts = scc_cnt = 0;
    for(int i = 1; i <= 2*n; i++) {
        graph[i].clear();
        ngraph[i].clear();
        dfn[i] = low[i] = id[i] = sz[i] = in_stk[i] = dp[i] = 0;
    }
    while(stk.size()) stk.pop();
}

void tarjan(int u) {
    dfn[u] = low[u] = ++ts;
    stk.push(u);
    in_stk[u] = true;
    for(int v: graph[u]) {
        if(!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }else if(in_stk[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(dfn[u] == low[u]) {
        ++scc_cnt;
        int y;
        do {
            y = stk.top();
            stk.pop();
            in_stk[y] = false;
            id[y] = scc_cnt;
            sz[scc_cnt]++;
        }while(y != u);
    }
}

int main() {
    scanf("%d", &T);
    while(T--) {
        init();
        scanf("%d%d", &n, &m);
        vector<array<int, 2>> edges;
        for(int i = 1; i <= m; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            if(u != v) {
                edges.push_back({u, v});
                graph[u].push_back(v);
            }else {
                // 自环
                edges.push_back({u, v + n});
                edges.push_back({v + n, u});
                graph[u].push_back(v + n);
                graph[v + n].push_back(u);
            }
        }
        // 先缩点
        tarjan(1);
        // 对强连通分量构建新图
        for(auto&edge: edges) {
            int u = edge[0], v = edge[1];
            if(id[u] != id[v]) {
                ngraph[id[u]].push_back(id[v]);
            }
        }
        // 在新图上DP，按拓扑序来
        if(sz[id[1]] > 1) {
            dp[id[1]] = -1;
        }else {
            dp[id[1]] = 1;
        }
        queue<int> q;
        q.push(id[1]);
        while(!q.empty()) {
            int cur = q.front();
            q.pop();
            for(int nxt: ngraph[cur]) {
                if(sz[nxt] > 1 || dp[cur] == -1) {
                    dp[nxt] = -1;
                }else if(dp[nxt] != -1) {
                    dp[nxt]++;
                }
                if(dp[nxt] <= 70) q.push(nxt);
            }
        }
        for(int i = 1; i <= n; i++) {
            if(!dfn[i]) {
                printf("%d ", 0);
            }else {
                printf("%d ", dp[id[i]] >= 2? 2: dp[id[i]]);
            }
        }
        puts("");
    }
    return 0;
}