考虑先找到一个原树的根。
对于第一种限制,\(b\) 不能作为根。
对于第二种限制,\(a\) 不能作为根。
找到可以作为根的一个点 \(rt\),显然由于限制互不矛盾肯定能找到。
对于第一种限制先直接连边。
考虑在满足第一种限制的前提下尽量满足第二种限制:让连通的点作为 \(rt\) 的一棵子树,不连通的点在 \(rt\) 的不同子树内。
然后让那些连通的点往下递归去做即可。
#include<bits/stdc++.h>
#define N 1010
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
struct data
{
int a,b;
data(){};
data(int aa,int bb){a=aa,b=bb;}
};
int n,m1,m2,res[N];
int fa[N],id[N];
bool tim[N],ban[N];
vector<data>v1,v2;
int find(int x)
{
return x==fa[x]?x:(fa[x]=find(fa[x]));
}
int solve(vector<int> p)
{
if(p.size()==1) return p[0];
memset(ban,0,sizeof(ban));
memset(tim,0,sizeof(tim));
for(int u:p) tim[u]=1,fa[u]=u;
for(int i=0;i<m1;i++)
if(tim[v1[i].a]&&tim[v1[i].b])
ban[v1[i].b]=1;
for(int i=0;i<m2;i++)
if(tim[v2[i].a]&&tim[v2[i].b])
ban[v2[i].a]=1;
int rt=-1;
for(int u:p)
{
if(!ban[u])
{
rt=u;
break;
}
}
assert(rt!=-1);
for(int i=0;i<m1;i++)
if(tim[v1[i].a]&&tim[v1[i].b]&&v1[i].a!=rt&&v1[i].b!=rt)
fa[find(v1[i].a)]=find(v1[i].b);
vector<vector<int> >pp;
for(int u:p)
{
if(u==rt) continue;
if(fa[u]==u)
{
id[u]=pp.size();
pp.push_back(vector<int>());
}
}
for(int u:p)
{
if(u==rt) continue;
pp[id[find(u)]].push_back(u);
}
for(auto np:pp) res[solve(np)]=rt;
return rt;
}
int main()
{
n=read(),m1=read(),m2=read();
for(int i=1;i<=m1;i++)
{
int a=read(),b=read();
v1.push_back(data(a,b));
}
for(int i=1;i<=m2;i++)
{
int a=read(),b=read();
v2.push_back(data(a,b));
}
vector<int>v;
for(int i=1;i<=n;i++) v.push_back(i);
int rt=solve(v);
for(int i=1;i<=n;i++)
if(i!=rt&&!res[i])
res[i]=rt;
for(int i=1;i<=n;i++)
printf("%d ",res[i]);
return 0;
}
标签:rt,pp,ch,int,构造,fa,read,reo,XSY2912
From: https://www.cnblogs.com/ez-lcw/p/16840740.html