标签：10005 cnt 原图 int 困难 back 造花 n1
- 考虑最终得到的图是一张“菊花图森林”，我们新增一个节点，向菊花图森林上的点随机连边，就能得到原图
- 这张原图可能很复杂，不好下手，但目标相对简单，我们考虑得到目标的必要条件
- 枚举原图中的每一条边（u,v)，如果存在x和u相连，y和v相连，这四个点要么形成一条长度>3的链，要么形成一个环，都与菊花图矛盾，必须至少删除一个点
- 如果找不到这样的(u,v)，说明原图就满足题意，删除任意点即可
点击查看代码
#include <bits/stdc++.h>
using namespace std;
vector<int>a[10005];
vector<int>c[10005];
int d[10005],sz[10005],ans[5],sum[10005];
bool v[10005];
int cnt,tot,n,m;
void dfs1(int n1)
{
v[n1]=true;
c[cnt].push_back(n1);
for(int i=0;i<a[n1].size();i++)
{
if(!v[a[n1][i]])
{
dfs1(a[n1][i]);
}
}
}
void dfs2(int n1)
{
v[n1]=true;
sz[n1]=1;
sum[n1]=(d[n1]==1);
for(int i=0;i<a[n1].size();i++)
{
if(v[a[n1][i]]==false)
{
dfs2(a[n1][i]);
sz[n1]+=sz[a[n1][i]];
sum[n1]+=sum[a[n1][i]];
}
}
}
bool pd(int n1)
{
for(int i=1;i<=n;i++)
{
v[i]=false;
}
for(int i=0;i<a[n1].size();i++)
{
d[a[n1][i]]--;
}
bool f=true;
v[n1]=true;
for(int i=0;i<a[n1].size();i++)
{
if(!v[a[n1][i]])
{
dfs2(a[n1][i]);
if(sum[a[n1][i]]==sz[a[n1][i]]-1||sz[a[n1][i]]==2&&sum[a[n1][i]]==2)
{
}
else
{
f=false;
break;
}
}
}
for(int i=0;i<a[n1].size();i++)
{
d[a[n1][i]]++;
}
return f;
}
void shuchu()
{
if(ans[0]==0)
{
cout<<-1<<"\n";
}
else
{
sort(ans+1,ans+ans[0]+1);
for(int i=1;i<=ans[0];i++)
{
cout<<ans[i]<<' ';;
}
cout<<"\n";
}
}
void solve(int x,int u,int v,int y)
{
if(pd(x))
{
ans[0]++;
ans[ans[0]]=x;
}
if(pd(u))
{
ans[0]++;
ans[ans[0]]=u;
}
if(pd(v))
{
ans[0]++;
ans[ans[0]]=v;
}
if(y!=x&&pd(y))
{
ans[0]++;
ans[ans[0]]=y;
}
shuchu();
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
a[i].clear();
c[i].clear();
v[i]=false;
d[i]=0;
}
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
a[u].push_back(v);
a[v].push_back(u);
d[u]++;
d[v]++;
}
cnt=0;
tot=0;
ans[0]=0;
for(int i=1;i<=n;i++)
{
if(!v[i])
{
cnt++;
dfs1(i);
}
}
int p=0;
for(int i=1;i<=cnt;i++)
{
int sum=0;
for(int j=0;j<c[i].size();j++)
{
sum+=(d[c[i][j]]==1);
}
if(sum+1==c[i].size()||sum==c[i].size()&&c[i].size()==2)
{
tot++;
}
else
{
p=i;
}
}
if(tot==cnt)
{
for(int i=1;i<=n;i++)
{
cout<<i<<' ';
}
cout<<"\n";
}
else if(tot==cnt-1)
{
bool f=false;
for(int i=0;i<c[p].size();i++)
{
int u=c[p][i];
for(int j=0;j<a[u].size();j++)
{
int v=a[u][j];
int x=0,y=0;
for(int k=0;k<a[u].size();k++)
{
if(a[u][k]!=v)
{
x=a[u][k];
break;
}
}
for(int k=0;k<a[v].size();k++)
{
if(a[v][k]!=u)
{
y=a[v][k];
break;
}
}
if(x&&y)
{
f=true;
solve(x,u,v,y);
break;
}
}
if(f==true)
{
break;
}
}
if(f==false)
{
for(int i=1;i<=n;i++)
{
cout<<i<<' ';
}
cout<<"\n";
}
}
else
{
cout<<-1<<"\n";
}
}
return 0;
}
标签：10005,
cnt,
原图,
int,
困难,
back,
造花,
n1
From： https://www.cnblogs.com/watersail/p/18382950