并查集简单题，赛前复习 :.....
附上代码：
1 /*************************************************************************
2 > File Name: 4496.cpp
3 > Author: Stomach_ache
4 > Mail: sudaweitong@gmail.com
5 > Created Time: 2014年05月19日 星期一 23时51分28秒
6 > Propose:
7 ************************************************************************/
8
9 #include <cmath>
10 #include <string>
11 #include <cstdio>
12 #include <fstream>
13 #include <cstring>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17
18 typedef pair<int, int> pii;
19 pii a[100005];
20 int ans[100005], fa[10005];
21
22 int
23 findSet(int x) {
24 return fa[x] != x ? fa[x]=findSet(fa[x]) : x;
25 }
26
27 int
28 main(void) {
29 int n, m;
30 while (scanf("%d %d", &n, &m) == 2) {
31 for (int i = 0; i < n; i++) {
32 fa[i] = i;
33 }
34 for (int i = 0; i < m; i++) {
35 scanf("%d %d", &a[i].first, &a[i].second);
36 }
37 ans[m] = n;
38 for (int i = m-1; i > 0; i--) {
39 int x = findSet(a[i].first);
40 int y = findSet(a[i].second);
41 if (x != y) {
42 fa[x] = y;
43 ans[i] = ans[i+1] - 1;
44 } else {
45 ans[i] = ans[i+1];
46 }
47 }
48 for (int i = 1; i <= m; i++) {
49 printf("%d
", ans[i]);
50 }
51 }
52
53 return 0;
54 }