DFS寻找有向图环的循环节点和多路径到达节点（CF1547G）
这道题从1开始出发去到达其他点v：
- 如果v点不能被到达则v的权值为0
- 从1到v有多条路径且数量有限则v的权值为2
- 从1到v只有1条路径则v的权值为1
- 从1到v有多条路径则v的权值为-1
题目给我们一个图，让我们将每个点的权值打印出来
首先我们可以通过一遍\(dfs\)来判断权值为0的点。然后我们怎么判断后面几种的区别呢？
如果对\(dfs\)的理解足够深刻的话，那么就会对点进行染色来解决这个问题：
-
我们将正在遍历的v点的子图时（从v点出发），将v点染色成灰色。
-
我们将完全遍历完v点的所有子图的时候，将v点染色成黑色
-
将还没遍历的点染色成白色（所以原本全是白色）
那么如果我们在遍历子网的时候，遇到了之前染过色的点
- 如果v这个点是黑色，说明有多条路径可以到达这个点v，这个点的权值是2
- 如果v这个点是灰色，说明v这个点在一个环内， v这个点权值是-1
但是上面判断出来的权值是1的点中不一定都真的是1， 这里有几个细节：
-
如果在我们判断出v点是-1，那么和v在同一个环内的点也是-1，从权值为-1的点出发达到的点权值也是-1 。
-
如果我们判断出一个点的权值是2，那么从这个点出发达到的点权值也是2
-
第一条优先于第二条
而判断的方式只是简单的\(dfs\)：（大佬牛逼）
// color是染色的点，1为灰，2为黑，0为白， flag是因为第一次判断出来的只是部分的点
//我们还需要多次dfs，将从-1和2延申出来的点给找出来，所以会用q1和q2两个队列进行记录起始点
void dfs(int u, int flag)
{
color[flag][u] = 1;
for(int i = head[u]; ~i; i = edge[i].next)
{
int v = edge[i].v;
if(color[flag][v] == 0) dfs(v, flag);
else if(flag == 0)
{
if(color[flag][v] == 1) q1.push(v);
else if(color[flag][v] == 2) q2.push(v);
}
}
color[flag][u] = 2;
}
正式题解：
首先用第一遍dfs将权值为0的点找出来，在找出部分权值为-1和2的起始点，存到队列中
再用暴力的方式将两个队列中经过的点记录下来。
-
如果第一次遍历是0说明不可达，权值一定是0 。
-
如果第一次权值不为0
- 第二次遍历（-1起始点）中经过这个点则为-1
- 如果第二次遍历没经过，但是第三次经过了，这为2
- 如果上述都没经过则为1
#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 4e5+10;
int dis[maxn];
int color[3][maxn];
int head[maxn];
int cnt;
queue<int> q1, q2;
struct Edge{
int u, v, next;
}edge[maxn];
void add(int u, int v)
{
edge[cnt].u = u;
edge[cnt].v = v;
edge[cnt].next = head[u];
head[u] = cnt++;
}
void ini(int n)
{
for(int i = 1; i <= n; i++)
dis[i] = color[0][i] = color[1][i] = color[2][i] = 0, head[i] = -1;
cnt = 0;
}
void dfs(int u, int flag)
{
color[flag][u] = 1;
for(int i = head[u]; ~i; i = edge[i].next)
{
int v = edge[i].v;
if(color[flag][v] == 0) dfs(v, flag);
else if(flag == 0)
{
if(color[flag][v] == 1) q1.push(v);
else if(color[flag][v] == 2) q2.push(v);
}
}
color[flag][u] = 2;
}
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
int n, m, u, v;
scanf("%d %d", &n, &m);
ini(n);
for(int i = 1; i <= m; i++)
{
scanf("%d %d", &u, &v);
add(u, v);
}
dfs(1, 0);
while(q1.size())
{
int u = q1.front();
q1.pop();
dfs(u, 1);
}
while(q2.size())
{
int u = q2.front();
q2.pop();
dfs(u, 2);
}
for(int i = 1; i <= n; i++)
{
int ans = 0;
if(color[0][i] != 0)
{
ans = 1;
if(color[1][i] != 0) ans = -1;
else if(color[2][i] != 0) ans = 2;
}
printf("%d ", ans);
}
}
return 0;
}