P10179题解

what_can_I_do · 2024-02-21 12:51:34 · 题解

传送门

其实题目要求的就是随便定一个点为根，则所有的 u_i 和 v_i 要么为兄弟关系，要么为爷孙关系。

那么此时我们就有一个策略，如果有一个点在所有的限制条件当中都没有出现，那么就可以另它为根，所有的点都是它的儿子，这样子就可以满足所有限制条件的点为兄弟关系。

如果没有这样的一个在所有的限制条件都没有出现的点呢？只需要给每个限制条件连边建图，然后从点 1 开始遍历点 1 的连通块，然后选择没在连通块的随便一个点为根，1 所在的连通块为这个点的儿子，其它的点为 1 的儿子，这样就可以保证所有不包括根的限制条件都能是兄弟关系且根的连通块里的点都跟它是爷孙关系。如果没有能选得出来的根就输出 No。

CODE:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t;
int n,m;
struct tree
{
    vector<int> son;
    int fa;
}tr[300010];
bool vis[300010]={0};
int uu[300010],vv[300010];
vector<int> g[300010];
queue<int> q;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        for(register int i=0;i<=n;i++) vis[i]=0,tr[i].fa=0,tr[i].son.clear(),g[i].clear();
        scanf("%d%d",&n,&m);
        if(!m)
        {
            for(register int i=1;i<=n-1;i++) printf("%d %d\n",i,i+1);
            continue;
        }
        for(register int i=1;i<=m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            uu[i]=u,vv[i]=v;
            vis[u]=vis[v]=1;
        }
        int ff=0;
        for(register int i=1;i<=n;i++) if(!vis[i]) ff=i;
        if(ff)
        {
            for(register int i=0;i<=n;i++) tr[i].son.clear();
            for(register int i=1;i<=n;i++)
            {
                if(i!=ff) tr[ff].son.push_back(i);
            }
        }
        else
        {
            for(register int i=1;i<=n;i++) vis[i]=0;
            for(register int i=1;i<=m;i++)
                g[uu[i]].push_back(vv[i]),g[vv[i]].push_back(uu[i]);
            q.push(1);
            while(!q.empty())
            {
                int k=q.front();
                q.pop();
                if(vis[k]) continue;
                vis[k]=1;
                for(register int i=0;i<g[k].size();i++)
                {
                    int x=g[k][i];
                    if(vis[x]) continue;
                    q.push(x);
                }
            }
            for(register int i=1;i<=n;i++) if(!vis[i]) ff=i;
            if(!ff){puts("No");continue;}
            for(register int i=2;i<=n;i++)
                if(vis[i]) tr[ff].son.push_back(i);
                else tr[1].son.push_back(i);
        }
        puts("Yes");
        for(register int i=1;i<=n;i++)
            for(register int j=0;j<tr[i].son.size();j++)
                printf("%d %d\n",i,tr[i].son[j]);
    }
    return 0;
}