Sgu/121

（转） 我们需从奇度顶点开始（如果没有从任意偶度顶点开始）给相临的边轮流染1、2色。 对于所有的奇数顶点我们一定可以满足，为什么呢？因为度数为1，肯定没有问题，度数>1的话，我们从此出发的话，假设先染白色，则一种颜色已经满足，只需另外一种。 分两种情况： 1.对于此顶点存在一个环路，如果是奇环，那么最后dfs回到此定点时的边的颜色应该是和刚开始染的白色一样，那么可想而知，我们最后肯定会剩下不是在环中的点（因为度数为奇），那么在从此节点出发的话，必然可以染出与前面一个不同的颜色（黑色），则这种情况是可以满足的；如果是偶环，那么最后回到此顶点的边的颜色必然是黑色，则同样满足题意。 2.对于不是环路，则很显然我们可以满足白，黑，白这样轮流的染色。 最后如果这样染出来的不行，则必然No solution。对于偶数顶点，我们只需依次染色，如果最后不满足的话，必然存在奇圈。

链接：http://hi.baidu.com/%B9%E3%C1%EAlonely%C9%A2/blog/item/6a6c0fb10ee5bea8d8335a74.html

#include <stdio.h>
using namespace std;
 
int n, map[101][101], deg[0];
int color[101][101];
 
void dfs(int i, int c)
{
     c = 3 - c;
     for (int k = 1; k <= deg[i]; ++k)
     {
         int j = map[i][k];
         if (!color[i][j])
         {
            color[i][j] = color[j][i] = c;
            dfs(j, c);
            c = 3 - c;
         }
     }
}
 
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        int j;
        while (scanf("%d", &j) && j)
              map[i][++deg[i]] = j;
    }
    for (int i = 1; i <= n; ++i)
        if (deg[i] & 1) dfs(i, 1);
    for (int i = 1; i <= n; ++i)
        dfs(i, 1);
    for (int i = 1; i <= n; ++i)
        if (deg[i] > 1)
        {
           int t = 0;
           for (int j = 1; j <= deg[i]; ++j)
               t |= color[i][map[i][j]];
           if (t != 3) {
              printf("No solution\n");
              return 0;
           }
        }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= deg[i]; ++j)
            printf("%d ", color[i][map[i][j]]);
        printf("0\n");
    }
    return 0;
}
// From FingerSed