LA 3644 并查集判断无向图是否有环

理解清楚题意以后就明白为什么要用并查集了。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int N = 100001;
 7 int f[N];
 8 int ans;
 9 
10 void init()
11 {
12     ans = 0;
13     for ( int i = 0; i < N; i++ )
14     {
15         f[i] = i;
16     }
17 }
18 
19 int findf( int x )
20 {
21     if ( f[x] != x ) f[x] = findf( f[x] );
22     return f[x];
23 }
24 
25 bool union_set( int x, int y )
26 {
27     x = findf(x), y = findf(y);
28     if ( x == y ) return false;
29     f[x] = y;
30     return true;
31 }
32 
33 int main ()
34 {
35     int x, y;
36     while ( scanf("%d%d", &x, &y) != EOF )
37     {
38         init();
39         f[x] = y;
40         while ( scanf("%d", &x), x != -1 )
41         {
42             scanf("%d", &y);
43             if ( !union_set( x, y ) )
44             {
45                 ans++;
46             }
47         }
48         printf("%d
", ans);
49     }
50     return 0;
51 }