Pursuit For Artifacts 题解

题目

• 给定一张 \(n\) 个点 \(m\) 条边的简单无向连通图，边有边权，边权要么为 \(0\)，要么为 \(1\)。
• 每条边只能通过一次（两个方向加起来只能通过一次）。
• 求是否存在一条从 \(a\) 到 \(b\) 的路径，满足路径上至少存在一条权为 \(1\) 的边。
• \(1 \leq n, m \leq 3 \times 10^5\)。

思路

因为是无向图，我们发现如果一个图里有边双连通分量，并且如果这个连通分量里只要有一条边1，那么这群点就可以全看做为1的点。于是首先，我们使用tarjan处理这个图，将其缩为边双连通分量。然后我们得到了一棵树，数的结点表示该连通分量。此时如果a和b在同一块连通分量，那么看一下这个连通分量里有没有边权为1的边即可，否则遍历这棵树，查询两点间路径里有没有权为1的点或权为1的边即可。

代码实现

#include<bits/stdc++.h>
#define fi first
#define se second
#define lowbit(x) (x&(-x))
using namespace std;
typedef pair<int,int> pii;
void solve(){
    int n,m;cin>>n>>m;
    vector<vector<pii>>e(n+1);
    while(m--){
        int u,v,w;cin>>u>>v>>w;
        e[u].emplace_back(v,w);
        e[v].emplace_back(u,w);
    }
    vector<int>dfsn(n+1),low(n+1),instk(n+1),scc(n+1);
    stack<int>stk;
    int dfscnt=0,sccnt=0;
    function<void(int,int)>tarjan=[&](int u,int fa){
        dfsn[u]=low[u]=++dfscnt;
        instk[u]=1;
        stk.push(u);
        for(auto v:e[u]){
            if(v.fi==fa)continue;
            if(!dfsn[v.fi]){
                tarjan(v.fi,u);
                low[u]=min(low[u],low[v.fi]);
            }
            else if(instk[v.fi])low[u]=min(low[u],dfsn[v.fi]);
        }
        if(dfsn[u]==low[u]){
            int temp;
            do{
                temp=stk.top();
                stk.pop();
                instk[temp]=0;
                scc[temp]=sccnt;
            }while(temp!=u);
            sccnt++;
        }
    };
    for(int i=1;i<=n;i++)if(!dfsn[i])tarjan(i,0);
    vector<int>col(sccnt);
    vector<vector<pii>>newe(sccnt);
    for(int i=1;i<=n;i++)
        for(auto j:e[i]){
            if(scc[i]==scc[j.fi]){
                if(j.se)col[scc[i]]=1;
            }
            else{
                newe[scc[i]].emplace_back(scc[j.fi],j.se);
            }
        }
    int x,y;cin>>x>>y;
    x=scc[x];y=scc[y];
    if(x==y){
        if(col[x])cout<<"YES\n";
        else cout<<"NO\n";
        return ;
    }
    int flag=0;
    function<void(int,int,int)>dfs=[&](int u,int f,int fa){
        f|=col[u];
        if(u==y){
            if(f){cout<<"YES\n";flag=1;return ;}
        }
        for(auto j:newe[u])if(j.fi!=fa)dfs(j.fi,f|j.se,u);
    };
     dfs(x,0,-1);
     if(!flag)cout<<"NO\n";
}
signed main(){
    std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
    srand((unsigned)time(NULL));
    //int t;std::cin>>t;while(t--)
    solve();
}