题目大意：给出一个无向图，每条边的边权是0或1，且只能走一次。询问从S到T的所有路径中，是否有一种路径上存在一条边权为1的点。

一开始想的是直接跑最长路，后来发现被轻易鏼掉，数据如下：

1 2 0

2 3 0

3 4 0

4 5 0

5 3 1

S=1 T=2

然后搜题解，是双连通分量缩点，然后就趁机学习了一下这个算法。

一个无向连通图，去掉一点或一边后影响了该图的连通性（本来是连通的，现在不连通了），则该点就是割点或该边就是桥。

把所有桥去掉后的连通块缩成一个点，在把桥连上就成一棵树。具体实现可以用tarjan求dfn和low，然后缩。

因为双连通分量，所以你走过去以后，一定可以走回来，或者说你肯定可以把这个连通分量的边都走一遍。

所以缩点以后只要每个点记录一个点权，然后S到T dfs一下就行了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 3e5 + 5;
int head[maxn], l=2;
int h[maxn << 1],V[maxn<<1],last[maxn<<1],t[maxn<<1];

void add(int u, int y, int z)
{
	t[l] = u;V[l] = z;h[l] = y;
    last[l] = head[u];
    head[u] = l++;
}

int n, m;
int dfn[maxn], low[maxn], cnt;
int St[maxn], is[maxn], Belong[maxn],N,st;
int A[maxn];
void tarjan(int x,int fa)
{
//	printf("%d",x);
	is[x] = 1;St[++st] = x;
	dfn[x] = low[x] = ++cnt;
	for (int i = head[x];i;i = last[i])
	{
		if ((i^1) == fa) continue;
		int j = h[i];
		if (!dfn[j]) tarjan(j,i),low[x] = min(low[x],low[j]);
		else if (dfn[j]<dfn[x]) low[x] = min(low[x],dfn[j]);
	}
	if (dfn[x] == low[x])
	{
		int v = St[st--];
	//	printf("%d",v);
        is[v] = 0;
        Belong[v] = ++N;
        for (;st && v != x;v = St[st--],is[v]=0,Belong[v] = N);
    }
}
int DFS(int st, int ed, int f, int s) {
    s |= A[st];
    if(st == ed) return s;
    for(int i = head[st];i; i = last[i])
	{
        int v = h[i];
        if(v == f) continue;
        if(DFS(v, ed, st, s | V[i])) return 1;
    }
    return 0;
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i = 1;i <= m;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	for (int i = 1;i <= n;i++)
		if (!dfn[i]) tarjan(i,-1);
	int etot = l;
	l = 1;memset(head,0,sizeof(head));
    for(int i = 1; i < etot;i++)
	{
        int u = Belong[t[i]],v = Belong[h[i]];
        if(u == v) A[u] |= V[i];
        else add(u, v, V[i]);
    }
    int st,ed;
    scanf("%d%d",&st,&ed);
    if(DFS(Belong[st],Belong[ed],-1,0)) puts("YES");
	else puts("NO");
    return 0;
}