Codeforces Round #731 (Div. 3) G. How Many Paths?

本文主要是介绍Codeforces Round #731 (Div. 3) G. How Many Paths?，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接： https://codeforces.com/contest/1547/problem/G
题意简述：给n个点m条边的有向图，求从1开始到每个结点的路径数量情况，0 - 无法到达， 1 - 一条路径， 2 - 多条路径， -1 - 无数条路径。在出现环的时候能有无限条路径。

题解：DFS的搜索中结点状态有3种：未被搜索到，正在扩展搜索，以及搜索完毕。根据DFS的特性，如果正在扩展的结点被再次访问，则说明存在环；如果以及搜索完毕的结点被再次访问，则说明有多条路径。
在环中的结点可以到达的点，一定是无限路径；多条路径的结点可以到达的点也一定是多条路径。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cstring>using namespace std;const int N = 4e5 + 5;int t, n, m;
int color[N];
int c[2][N];vector<vector<int>> e;
vector<int> group[2];void dfs1(int u) {color[u] = 1;for (auto v : e[u]) {if (color[v] == 0) dfs1(v);elsegroup[color[v] - 1].push_back(v);}color[u] = 2;
}void dfs2(int u, int i) {c[i][u] = 1;for (auto v : e[u]) if (c[i][v] == 0)dfs2(v, i);c[i][u] = 2;
}int main(void) {// freopen("in.txt", "r", stdin);scanf("%d", &t);while (t--) {scanf("%d%d", &n, &m);e = vector<vector<int>>(n + 1);memset(color, 0, sizeof(color));memset(c, 0, sizeof(c));group[0].clear();group[1].clear();for (int i = 0; i < m; i++) {int a, b;scanf("%d%d", &a, &b);e[a].push_back(b);}dfs1(1);for (int i = 0; i < 2; i++)for (auto u: group[i])dfs2(u, i);for (int i = 1; i <= n; i++) {int ans = 0;if (color[i]) {ans = 1;if (c[0][i])ans = -1;else if (c[1][i])ans = 2;}printf("%d%c", ans, i == n ? '\n' : ' ');}}return 0;
}