【Codeforces 652E】Pursuit For Artifacts

  首先把桥边给找出来，因为经过一条边以后整个图就不连通的，也就是分成了两块，那么这条边一定是桥边。另外，如果一条边不是桥边，那么只经过这一条边就不会对其他点的连通性造成影响。

  然后把那些类似双联通分量的东西缩点，这样缩完以后是一棵树。（如果不是一棵树，那么就一定有一个环，把那个环缩起来还是一棵树）

  因为在一个双联通分量中，固定起点与终点，然后必须要经过一条有物品的边，这是肯定可以走的。（大概可以把它想象成一个环之类的）

  然后在树上DFS一遍就好了。如果出多组询问，开个线段树记录一下树上的信息就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=300010;

struct Graph
{
	int head[maxn],next[maxn<<1],E[maxn<<1],D[maxn<<1],Ecnt;
	void Add_Edge(int x,int y,int z) {next[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;D[Ecnt]=z;next[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;D[Ecnt]=z;}
}G,T;

int n,m,S,E;

int DFN[maxn],Low[maxn],dcnt;
int Stack[maxn],top;
int belong[maxn],bcnt;

void DFS(int x,int fa)
{
	DFN[x]=Low[x]=++dcnt;
	Stack[++top]=x;
	for (int i=G.head[x];i;i=G.next[i]) if (G.E[i]!=fa)
		if (!DFN[G.E[i]]) DFS(G.E[i],x),Low[x]=min(Low[x],Low[G.E[i]]);
		else Low[x]=min(Low[x],DFN[G.E[i]]);
	if (DFN[x]==Low[x])
	{
		++bcnt;
		while (Stack[top]!=x) belong[Stack[top--]]=bcnt;
		belong[Stack[top--]]=bcnt;
	}
}

int v[maxn];
int ans;

void DFS2(int x,int fa,int res)
{
	if (x==belong[E]) ans=res;
	for (int i=T.head[x];i;i=T.next[i]) if (T.E[i]!=fa) DFS2(T.E[i],x,res|T.D[i]|v[T.E[i]]);
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1,x,y,z;i<=m;i++) scanf("%d%d%d",&x,&y,&z),G.Add_Edge(x,y,z);
	scanf("%d%d",&S,&E);
	DFS(1,0);
	for (int x=1;x<=n;x++)
		for (int i=G.head[x];i;i=G.next[i]) if (belong[x]==belong[G.E[i]]) v[belong[x]]|=G.D[i];else if (belong[x]<belong[G.E[i]]) T.Add_Edge(belong[x],belong[G.E[i]],G.D[i]);
	DFS2(belong[S],0,v[belong[S]]);
	if (ans) puts("YES");else puts("NO");
	return 0;
}