TOJ 101 哪裡有卦，哪裡就有源 ( 水題二分圖 )

http://sprout.tw/oj/pro/101/
顯然就是二分圖。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXM = 2 * MAXN;

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

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

int col[ MAXN ];

bool bip(int u){
    for(int v: G[ u ]){
        if( col[ u ] == col[ v ] ) return false;
        if( col[ v ] ) continue;
        col[ v ] = 3 - col[ u ];
        if( !bip( v ) ) return false;
    }
    return true;
}

void solve(){
    memset( col, 0, sizeof(col) );
    for(int i = 0; i < n; ++i) if( !col[ i ] ){
        col[ i ] = 1;
        if( !bip( i ) )
            return (void)puts("RAINBOW.");
    }
    puts("NORMAL.");
}

int main(){
    while( scanf("%d", &n) && n ){
        init();
        int m; scanf("%d", &m);
        for(int i = 0; i < m; ++i){
            int u, v; scanf("%d%d", &u, &v);
            G[ u ].push_back( v );
            G[ v ].push_back( u );
        }
        solve();
    }
    return 0;
}