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; }