求助!代码有注释和思路
查看原帖
求助!代码有注释和思路
308384
Morpheuse楼主2022/2/3 22:45
#include<bits/stdc++.h>
using namespace std;
#define maxn 500010
/*
把环缩成点 环中有一条为 1 的边 那么缩成的点为 1.
O(n) dfs找a b 路径上是否存在至少一个为 1 的点或者边. 
*/
struct node
{
	int to , data , next;
}e[maxn << 1];
int head[maxn],idk = 1;//从序号2开始记边 方便无向图缩点的时候判断边是否走过 
inline void add(int x , int y , int z)
{
	e[++ idk].data = z;
	e[idk].next = head[x];
	e[idk].to = y;
	head[x] = idk;
}
int bok[maxn];
int dfn[maxn],low[maxn],num,st[maxn],top,clo[maxn];
int cnt,vis[maxn << 1],scc[maxn];
void tarjan(int x)
{
	dfn[x] = low[x] = ++ num;
	st[++ top] = x;
	for(int i = head[x] ; i ; i = e[i].next)
	{
		int to = e[i].to;
		if(vis[i] == 1) continue;
		vis[i] = vis[i ^ 1] = 1;//记录这条无向边已经走过     
		if(dfn[to] == 0)
		{
			tarjan(to);
			low[x] = min(low[x] , low[to]);
		}
		else low[x] = min(low[x] , dfn[to]);
	}
	if(dfn[x] == low[x])
	{
		cnt ++;
		while(st[top] != x)
		{
			scc[st[top]] = cnt;
			top --;
		}
		scc[st[top]] = cnt;
		top --;
	}
}

void dfs(int x , int s)
{//如果这个环里面有一条边为 1 那整个环都是 1 
	bok[x] = 1;
	if(s == 1) clo[scc[x]] = 1;
	for(int i = head[x] ; i ; i = e[i].next)
		if(bok[e[i].to] == 0 && scc[e[i].to] == scc[x])
			dfs(e[i].to , (s || e[i].data));
}
int a,b;
void init()
{
	memset(e , 0 , sizeof(e));
	memset(head , 0 , sizeof(head));
	idk = 0;
}

void ans(int x , int flag , int f)
{
	if(clo[x]) flag = 1;
	if(x == scc[b])
	{
		if(flag) printf("YES");
		else printf("NO");
		return;
	}
	for(int i = head[x] ; i ; i = e[i].next)
	{
		int to = e[i].to;
		if(to == f) continue;
		ans(to , (flag || e[i].data) , x);
	} 
}

inline int read()
{
	int f = 1 , x = 0 ; char c = getchar();
	while(c < '0' || c > '9') f = (c == '-' ? -1 : 1) , c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - '0' , c = getchar();
	return x * f;
}

int x[maxn],y[maxn],z[maxn];
int n,m;
int main()
{
	n = read() , m = read();
	for(int i = 1 ; i <= m ; ++ i)
	{
		x[i] = read() , y[i] = read() , z[i] = read();
		add(x[i] , y[i] , z[i]);
		add(y[i] , x[i] , z[i]);
	}
	
	for(int i = 1 ; i <= n ; ++ i)
		if(dfn[i] == 0)
			tarjan(i);//缩点 
	
	for(int i = 1 ; i <= n ; ++ i)
		if(bok[i] == 0)
			dfs(i , 0);//判断环内是否有边为 1 
	init();//清空原图 
	for(int i = 1 ; i <= m ; ++ i)
		if(scc[x[i]] != scc[y[i]])
			add(scc[x[i]] , scc[y[i]] , z[i]) , add(scc[y[i]] , scc[x[i]] , z[i]);//重新建图 
	a = read() , b = read();
	
	ans(scc[a] , 0 , 0);//O(n)找答案 
}
2022/2/3 22:45
加载中...