并查集 之 CODE[VS] 1073 家族

/*
并查集
*/
  1 #include <iostream>
  2 #include <cstdlib>
  3 #include <cstdio>
  4 #include <cstddef>
  5 #include <iterator>
  6 #include <algorithm>
  7 #include <string>
  8 #include <locale>
  9 #include <cmath>
 10 #include <vector>
 11 #include <cstring>
 12 #include <map>
 13 #include <utility>
 14 #include <queue>
 15 #include <stack>
 16 #include <set>
 17 #include <functional>
 18 using namespace std;
 19 typedef pair<int, int> PII; 
 20 const int INF = 0x3f3f3f3f;
 21 const int modPrime = 3046721;
 22 const double eps = 1e-9;
 23 const int MaxN = 5010;
 24 const int MaxM = 5010;
 25 
 26 int N, M, P;
 27 /******************************************/
 28 // 并查集:Union-Find Sets
 29 int ftr[MaxN];
 30 int rnk[MaxN];
 31 void ufsIni(int n)
 32 {
 33     for (int i = 0; i <= n; ++i)
 34     {
 35         ftr[i] = i;
 36     }
 37 }
 38 
 39 int ufsFind(int x)
 40 {
 41     if (x == ftr[x])
 42     {
 43         return x;
 44     }
 45     return ftr[x] = ufsFind(ftr[x]);
 46 }
 47 
 48 void ufsUnite(int x, int y)
 49 {
 50     x = ufsFind(x);
 51     y = ufsFind(y);
 52     if (x == y)
 53     {
 54         return;
 55     }
 56 
 57     if (rnk[x] < rnk[y])
 58     {
 59         ftr[x] = y;
 60     }
 61     else
 62     {
 63         ftr[y] = x;
 64         if (rnk[x] == rnk[y])
 65         {
 66             ++rnk[x];
 67         }
 68     }
 69 }
 70 
 71 bool ufsSame(int x, int y)
 72 {
 73     return (ufsFind(x) == ufsFind(y));
 74 }
 75 
 76 /******************************************/
 77 
 78 void Solve()
 79 {
 80     ufsIni(N);
 81     int x, y;
 82     for (int i = 0; i < M; ++i)
 83     {
 84         scanf("%d %d", &x, &y);
 85         ufsUnite(x, y);
 86     }
 87     for (int i = 0; i < P; ++i)
 88     {
 89         scanf("%d %d", &x, &y);
 90         if (ufsSame(x, y))
 91         {
 92             printf("Yes
");
 93         }
 94         else 
 95         {
 96             printf("No
");
 97         }
 98     }
 99 }
100 
101 int main()
102 {
103 #ifdef HOME
104     freopen("in", "r", stdin);
105     //freopen("out", "w", stdout);
106 #endif
107 
108     scanf("%d %d %d", &N, &M, &P);
109     Solve();
110 
111 #ifdef HOME
112     cerr << "Time elapsed: " << clock() / CLOCKS_PER_SEC << " ms" << endl;
113     _CrtDumpMemoryLeaks();
114 #endif
115     return 0;
116 }



原文地址:https://www.cnblogs.com/shijianming/p/5043289.html