写的ｄｆｓ貌似不太对 ｂｆｓ重写
用ｂｆｓ将图进行黑白染色 如果有超过一个与自己颜色相同的点 就把该点存入栈中 最后处理栈中的点 判断此点是否合法 不合法 取反 取反后再判断相邻点是否合法 不合法再存入栈中 直到栈为空
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<queue>
using namespace std;
#define N 80010
vector<int>ed[N];
int n;
int vis[N],d[N],f[N],g;
void bfs(int s)
{
int i;
queue<int>q;
q.push(s);
vis[s] = ;
while(!q.empty())
{
int u = q.front();
q.pop();
int k = vis[u];
int num = ;
for(i = ; i < (int)ed[u].size() ;i++)
{
int v = ed[u][i];
if(!vis[v])
{
vis[v] = -k;
q.push(v);
}
else if(vis[v]!=-k)
{
num++;
}
}
if(num>)
{
g++;
d[g] = u;
}
}
}
int main()
{
int m,i,j;
scanf("%d",&n);
for(i = ; i <= n ; i++)
{
scanf("%d",&m);
for(j = ; j <= m ; j++)
{
int a;
scanf("%d",&a);
ed[i].push_back(a);
}
}
for(i = ; i <= n ; i++)
{
if(!vis[i]&&!f[i])
{
bfs(i);
}
}
for(i = ; i <= g ; i++)
{
int v = d[i],num=;
for(j = ; j < (int)ed[v].size() ; j++)
{
int x = ed[v][j];
if(vis[x]==vis[v])
num++;
}
if(num>)
{
vis[v] = -vis[v];
for(j = ; j < (int)ed[v].size() ; j++)
{
int x = ed[v][j],oo=;
for(int p = ; p < (int)ed[x].size() ; p++)
if(vis[x]==vis[ed[x][p]])
{
oo++;
}
if(oo>)
{
g++;
d[g] = x;
}
}
}
}
int num = ,o=-,t;
for(i = ; i <= n ; i++)
if(vis[i]==)
{
if(i==)
o = ;
num++;
}
if(num<n-num)
{
t = ;
}
else if(num==n-num)
{
t = o;
}
else
{
num = n-num;
t = -;
}
printf("%d\n",num);
for(i = ; i <= n ; i++)
if(vis[i]==t)
printf("%d ",i);
puts("");
return ;
}