周源的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。感谢周天皇。

?[Copy to clipboard]View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

#include <cstdio>
#include <list>
using namespace std;
 
struct point
{
    int c,d,pre;
    list<int> ge,te;
    point():c(0),d(0),pre(0){};
} graph[101];
 
void dfs(int id)
{
    for (list<int>::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<int>::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<int>::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<int>::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;
}