首页 > 代码库 > Hdu 4496
Hdu 4496
题目链接
并查集简单题,赛前复习 :.....
附上代码:
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\n", ans[i]);
50 }
51 }
52
53 return 0;
54 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。