并查集

  1 /*
  2 2015.6    HT
  3 ACM Work_7
  4 
  5 */
  6 
  7 #include <iostream>
  8 #include <cstdio>
  9 #include <cstring>
 10 using namespace std;
 11 
 12 
 13 /*
 14 How Many Tables
 15 并查集
 16 For example:
 17 If I tell you A knows B, B knows C, and D knows E, so A, B, C can stay in one table,
 18 and D, E have to stay in the other one. So needs 2 tables at least
 19 */
 20 //int parent[1002];
 21 //
 22 //void init(int n)
 23 //{
 24 //    for (int i = 1; i <= n; i++)
 25 //        parent[i] = i;
 26 //}
 27 //
 28 //int find(int x)
 29 //{
 30 //    if (x != parent[x])
 31 //        parent[x] = find(parent[x]);
 32 //    return parent[x];
 33 //    //return parent[x] == x ? x : find(parent[x]);
 34 //}
 35 //
 36 //void unite(int x, int y)
 37 //{// 合并
 38 //    x = find(x);
 39 //    y = find(y);
 40 //    if (x == y)
 41 //        return;
 42 //    else
 43 //        parent[x] = y;
 44 //}
 45 //
 46 //int main()
 47 //{
 48 //    int t, n, m, a, b, ans;
 49 //    cin >> t;
 50 //    while (t--)
 51 //    {
 52 //        cin >> n >> m;
 53 //        init(n);
 54 //        ans = 0;
 55 //        for (int i = 1; i <= m; i++)
 56 //        {
 57 //            cin >> a >> b;
 58 //            unite(a, b);
 59 //        }
 60 //        for (int i = 1; i <= n; i++)
 61 //        {
 62 //            if (parent[i] == i)
 63 //                ans++;
 64 //        }
 65 //        cout << ans << endl;
 66 //    }
 67 //    return 0;
 68 //}
 69 
 70 
 71 
 72 /*
 73 小希的迷宫
 74 
 75 */
 76 //int parent[100002], k;
 77 //
 78 //struct sum
 79 //{
 80 //    int a, b;
 81 //}num[100002];
 82 //
 83 //int Find(int x)  
 84 //{
 85 //    while (x != parent[x])
 86 //        x = parent[x];
 87 //    return x;
 88 //}
 89 //
 90 //void Unite(int x, int y)
 91 //{
 92 //    x = Find(x);
 93 //    y = Find(y);
 94 //    if (x != y)
 95 //        parent[x] = y;
 96 //    else
 97 //        k = 0;
 98 //}
 99 //
100 //int main()
101 //{
102 //    int m, n, i;
103 //    memset(parent, 0, sizeof(parent));
104 //    i = 0;
105 //    while (cin >> m >> n)
106 //    {
107 //        if (m == -1 && n == -1)
108 //            break;
109 //        num[i].a = m;
110 //        num[i].b = n;
111 //        parent[m] = m;
112 //        parent[n] = n;
113 //        i++;
114 //        if (m == 0 && n == 0)
115 //        {
116 //            // 输入了n组
117 //            n = i - 1;
118 //            if (n == 0)
119 //            {// 只有一组数据 Yes
120 //                cout << "Yes\n";
121 //                i = 0;
122 //                memset(parent, 0, sizeof(parent));
123 //                continue;
124 //            }
125 //            k = 1;
126 //            for (i = 0; i<n; i++)
127 //            {// 合并
128 //                Unite(num[i].a, num[i].b);
129 //            }
130 //
131 //            int t = 0;
132 //            for (i = 1; i <= 100002; i++)
133 //            {
134 //                if (parent[i] == i)
135 //                    t++;
136 //            }
137 //            if (t != 1)
138 //                cout << "No\n";
139 //            else
140 //            {
141 //                if (k)
142 //                    cout << "Yes\n";
143 //                else
144 //                    cout << "No\n";
145 //            }
146 //            i = 0;
147 //            memset(parent, 0, sizeof(parent));
148 //        }
149 //    }
150 //    return 0;
151 //}
152 
153 
154 
155 /*
156 畅通工程
157 
158 */
159 int parent[1002];
160 
161 int find(int x)
162 {
163     while (x != parent[x])
164         x = parent[x];
165     return x;
166 }
167 
168 void unite(int x, int y)
169 {
170     x = find(x);
171     y = find(y);
172     if (x != y)
173         parent[x] = y;
174 }
175 
176 int main()
177 {
178     int n, m, i, x, y, count;
179     while (cin >> n && n)
180     {
181         for (i = 1; i <= n; i++)
182             parent[i] = i;
183         for (cin >> m; m>0; m--)
184         {
185             cin >> x >> y;
186             unite(x, y);
187         }
188         for (count = -1, i = 1; i <= n; i++)
189         if (parent[i] == i)
190             count++;
191         cout << count << endl;
192     }
193 }