ural 1106，二分图染色，DFS

题目链接：http://acm.timus.ru/problem.aspx?space=1&num=1106

乍一眼看上去，好像二分图匹配，哎，想不出和哪一种匹配类似，到网上查了一下，DFS染色一遍就可以啦。

两种颜色的很好写。直接没有访问的是1，然后扫邻接表，为2，DFS邻接表。

#include <bits/stdc++.h>
using namespace std;
#define maxn 105
vector<int> G[maxn];
int color[maxn],vis[maxn];
void dfs(int u)
{
vis[u] = 1;
for(int i=0;i<G[u].size();i++)
{
int v = G[u][i];
if(!vis[v])
{
color[v] = 3 - color[u];
dfs(v);
}
}
}
int main()
{
int n,t;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
while(scanf("%d",&t),t)
G[i].push_back(t);
}
memset(vis,0,sizeof(vis));
memset(color,0,sizeof(color));
for(int i=1;i<=n;i++)
{
if(vis[i]==false)
{
color[i] = 1;
dfs(i);
}
}
int sum = 0;
for(int i=1;i<=n;i++)
if(color[i]==1)
sum++;
printf("%dn",sum);
for(int i=1;i<=n;i++)
if(color[i]==1)
printf("%d ",i);
return 0;
}