基础的带权并查集,也是入门的种类并查集,具体做法参考poj 1182 食物链
#include <map> #include <set> #include <queue> #include <stack> #include <vector> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define lson l, mid, rt << 1 #define rson mid + 1, r, rt << 1 | 1 #define pi acos(-1.0) #define eps 1e-8 typedef long long ll; const int inf = 0x3f3f3f3f; const int N = 2200; int n, m; bool OK; struct node{ int fa, re; }a[N]; void init( ) { for( int i = 1; i <= n; ++i ) { a[i].fa = i; a[i].re = 0; } OK = 0; } int dfs( int x ) { if( x == a[x].fa ) return x; int fa = a[x].fa; a[x].fa = dfs( fa ); a[x].re = ( a[fa].re + a[x].re ) % 2; return a[x].fa; } void Union( int x, int y ) { int xx = dfs( x ); int yy = dfs( y ); if( xx == yy ) return; a[xx].fa = yy; a[xx].re = ( ( (1 - a[x].re) + a[y].re ) % 2 + a[yy].re ) % 2; } int main() { int tot, cas = 0; scanf("%d", &tot); while( tot-- ) { scanf("%d%d", &n, &m); init(); int u, v; while ( m-- ) { scanf("%d%d", &u, &v); if( OK ) continue; int uu = dfs( u ); int vv = dfs( v ); if( uu == vv ) { if( (a[u].re + a[v].re ) != 1 ) { OK = 1; } } else { Union( u, v ); } } printf("Scenario #%d:\n", ++cas ); if( OK ) puts("Suspicious bugs found!"); else puts("No suspicious bugs found!"); puts(""); } return 0; }