UVA 11396 Claw Decomposition ( 水題二分圖判定 )

UVa Online Judge
正確率挺高的果然只是個裸二分圖判定。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300 + 3;

int n;
vector<int> G[MAXN];

struct Bipartite{
    int col[MAXN];
    void init(){
        memset( col, 0, sizeof(col) );
    }
    bool canBip(int u){
        for(int v: G[u]){
            if( col[v] == col[u] ) return false;
            if( !col[v] ){
                col[ v ] = 3 - col[ u ];
                if( !canBip( v ) ) return false;
            }
        }
        return true;
    }
} bip;

void solve(){
    bip.init();
    for(int u = 1; u <= n; ++u)
        if( !bip.col[ u ] ){
            bip.col[ u ] = 1;
            if( !bip.canBip( u ) ){
                puts("NO");
                return;
            }
        }
    puts("YES");
}

void init(){
    for(int u = 1; u <= n; ++u)
        G[u].clear();
}

int main(){
    while( scanf("%d", &n) == 1 && n ){
        init();
        for(;;){
            int u, v; scanf("%d%d", &u, &v);
            if( u + v == 0 ) break;
            G[ u ].push_back( v );
            G[ v ].push_back( u ); // 1-idx
        }
        solve();
    }
    return 0;
}