周源的SGU表格已经叙述的非常详细了:(内容有字句上的修改)
  给定一个无向图,要求给这个图上的边0、1染色,且保证每个度不小于2的点都至少能连出一条0边,也至少能连出一条1边。
  可以知道,这个图上可能会出现很多连通块,而两个连通块之间是不会互相影响的,所以可以分别处理之。
  对某一个连通块,可以随便选择一个点,对这个图进行深度优先搜索建树,并将这棵树分层:根节点为第0层,根节点的孩子为第1层,以此类推……
  于是树上的每一条边也可能得到一个层数:根节点连出的边为第1层,根节点的孩子连向它们孩子的边为第2层,等等。即第i层节点和它们的父亲所连的边可以称为第i层。
  如果在深度优先搜索树中,根节点有多个孩子:即根节点是一个“关键点”,那么问题就好办了:在根节点root连出去的多个孩子中,选出一个孩子p,让边root-p的颜色为0,其余根节点连出的树上的边的颜色是1。接着处理其他树上的边:如果这条边是p的子树上的,那么它的颜色就是其(层数+1) mod 2,否则颜色就是层数 mod 2。而叶子节点连出的回边,可以根据叶子节点现在“缺少”的颜色来确定,这样就能保证叶子节点连出去的边符合题意。而图中的其他边,可以任意染色:因为无论如何,这个染色方案都是符合题意的了。
  另外一种情况,就是根节点只有一个孩子了,首先一样处理树上的边,让其颜色为其层数 mod 2。树上所有点连出的回边,颜色可为这个点的(层数+1) mod 2。这样的染色方法,可能有情况会导致构造出来的解释错误的,即根节点在原图上的度大于等于2,但所有能连向根节点的回边的颜色都是1:它们的另一个端点都在偶数层。当然,如果有一条连向根回边的另一个端点不是叶子节点,那么这个回边的染色方法是自由的:将其染为0色并不影响其他节点,却又得到了正确的答案。但是,如果所有这样的回边都是由叶子节点连出的呢?不妨随便选择一个这样的叶子节点,沿着深度优先搜索树不停的向上找,直到找到某一个祖先节点的度大于2,这个时候,将这条回溯路径上的边、以及叶子节点连向根的回边的颜色全部反色,就可以得到正确的答案了。最后可能有人会问:如果找不到度大于2的点呢?那么显然此时这个图是一个奇环:这是一定无解的。
  这样,我们就得到了一个正确的算法了,其时间复杂度为O(N+E),空间复杂度为O(E)。

  Submit 1: WA on 9。叶子节点连出的回边也要处理,都写成无所谓的颜色是不行的。比如下面这个图:
7
2 5 0
1 3 7 0
2 4 6 0
3 5 0
1 4 0
3 7 0
2 6 0
2-7那条边,就不能归为“无所谓”。
  Submit 2: AC。感谢周天皇。


#include
#include using namespace std;

struct point
{
int c,d,pre;
list ge,te;
point():c(0),d(0),pre(0){};
} graph[101];

void dfs(int id)
{
for (list::iterator i=graph[id].ge.begin();i!=graph[id].ge.end();++i) if (!graph[*i].pre)
{
graph[*i].pre=id; graph[id].te.push_back(*i);
dfs(*i);
}
}

bool clean_up(int id)
{
if (id!=graph[id].pre)
{
if (graph[id].te.size()<2) { graph[id].c=!graph[id].c; return clean_up(graph[id].pre); } else return true; } else return false; } bool color(int id,bool c,bool rootc,bool need_clean_up) { list::iterator i=graph[id].te.begin();
if (id==graph[id].pre)
{
need_clean_up=(graph[id].te.size()==1);
graph[*i].c=c;
if (!color(*i,c,c,need_clean_up)) return false;
++i;
}
for (;i!=graph[id].te.end();++i)
{
graph[*i].c=!c;
if (!color(*i,!c,rootc,need_clean_up)) return false;
}
if (need_clean_up && graph[id].te.size()==0 && graph[id].c!=rootc)
for (list::iterator i=graph[id].ge.begin();i!=graph[id].ge.end();++i)
if (*i==graph[*i].pre) return clean_up(id);
return true;
}

int main()
{
int n;
scanf("%d",&n);
for (int i=1;i<=n;i++) { int t; scanf("%d",&t); while (t) { graph[i].d++; graph[i].ge.push_back(t); scanf("%d",&t); } } for (int i=1;i<=n;i++) if (graph[i].pre==0 && graph[i].d) { graph[i].pre=i; dfs(i); if (!color(i,0,0,0)) { printf("No solution\n"); return 0; } } for (int j=1;j<=n;j++) { for (list::iterator i=graph[j].ge.begin();i!=graph[j].ge.end();++i)
{
if (graph[*i].pre==j) printf("%d ",graph[*i].c+1);
else if (graph[j].pre==*i) printf("%d ",graph[j].c+1);
else if (graph[*i].te.size()==0) printf("%d ",!graph[*i].c+1);
else if (graph[j].te.size()==0) printf("%d ",!graph[j].c+1);
else printf("2 ");
}
printf("0\n");
}
return 0;
}