求助佬帮忙debug,参考了8943的做法,但还是过不了,不知道哪里错了
查看原帖
求助佬帮忙debug,参考了8943的做法,但还是过不了,不知道哪里错了
816017
zhenghao9103楼主2023/10/5 19:42
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define pb push_back
#define pii pair<int,int>
const int N=2e5+5;
int T;
int n,a,b;
int deg[N],st[N],dep[N],top[N],loop[N];
int idx;
vector<int>e[N];
void dfs(int u,int fa,int tp)
{
    
    top[u]=tp;
    st[u]=1;
    for(auto v:e[u])
    {
        if(v==fa||st[v]) continue;
        dep[v]=dep[u]+1;
        dfs(v,u,tp);
    }
}
void getloop()
{
    queue<int>q;
    for(int i=1;i<=n;i++)
    {
        if(deg[i]==1) q.push(i);
    }
    while(q.size())
    {
        int u=q.front();
        q.pop();
        for(auto v:e[u])
        {
            deg[v]--;
            if(deg[v]==1) q.push(v);
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(deg[i]==2)
        {
            st[i]=1;
            loop[++idx]=i;
        }
    }
}
void init()
{
    for(int i=1;i<=n;i++)
        deg[i]=0,dep[i]=0,st[i]=0,top[i]=0,e[i].clear();
        idx=0;
}
void solve()
{

    cin>>n>>a>>b;
    init();
    for(int i=1;i<=n;i++)
    {
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
        deg[u]++,deg[v]++;
    }
      if(a==b)
    {
        cout<<"no"<<endl;
        return ;
    }
    getloop();
    if(st[b])
    {
        cout<<"yes"<<endl;
        return ;
    }
    for(int i=1;i<=idx;i++)
    {
        dfs(loop[i],0,i);
    }
    int x=dep[a],y=dep[b];
    int len=abs(top[a]-top[b]);
    if(y<x+min(len,idx-len))
    {

        cout<<"yes"<<endl;
    }
    else cout<<"no"<<endl;
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}


2023/10/5 19:42
加载中...