SGU 121 Bridges painting

想到一個解法，傳上去也AC了

想一想發現居然有錯OAO

網路上也有一堆人都是錯的

決定改成用周源的作法重寫一遍～

====================================

做一個DFS樹：

選第一個節點連黑，其餘皆連紅，分層塗色

若有回溯邊，就連他沒有連過的顏色。

如果根節點只有一個子節點：

選一個連到根的回溯邊，將他變成紅色

若其為葉子，往上不斷的換顏色，直到該點有連出不只兩條邊

若找不到，puts("No solution")

//By momo
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 110
#define FOR(it, c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();it++)
using namespace std;

vector<int> G[N];
int n, vs[N], clr[N][N], fa[N], lf[N];

void CC(int a, int b, int c){ clr[a][b] = clr[b][a] = c+1; }

void dfs(int p, int f, int c){
    fa[p] = f;
    vs[p] = 1;
    CC(f, p, c);
    FOR(it, G[p]){
        if(vs[*it]){
            if(clr[p][*it] == 0) CC(p, *it, c^1);
            continue;
        }
        dfs(*it, p, c^1);
        lf[p] = 0;
    }
}

bool solve(){
    for(int i = 0; i < n; i++){
        if(vs[i]) continue;
        int cnt = 0;
        vs[i] = 1;
        FOR(it, G[i]){
            if(vs[*it]) continue;
            dfs(*it, i, (cnt&&1)); cnt++;
        }
        if(cnt != 1 || G[i].size() == 1) continue;
        int nx = G[i][1];
        if(lf[nx]){
            int x = nx, c;
            CC(i, x, c = 1);
            for(; x != i && G[x].size() == 2; x = fa[x])
                CC(x, fa[x], c ^= 1);
            if(x == i) return 0;
        }
        else CC(i, nx, 1);
    }
    return 1;
}

void input(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        int x; lf[i] = 1;
        while(scanf("%d", &x), x != 0) G[i].push_back(x-1);
    }
}

void output(){
    for(int i = 0; i < n; i++){
        FOR(it, G[i]) printf("%d ", clr[i][*it]);
        puts("0");
    }
}

int main(){
    input();
    if(solve()) output();
    else puts("No solution");
}