首页 > 代码库 > hdu 4496 D-City(并查集)
hdu 4496 D-City(并查集)
题目:hdu 4496 D-City
题目大意:n代表n座城市,m代表m条关系。刚开始所有的城市都是连在一起的,这样就是一个联通分量,然后给出m条关系,每条关系x y 代表x y之间有一条通道使两座城市相连,问按顺序去掉这样的通道后,每次去掉一条会变成几个联通分量。
解题思路:这题题目保证最后一定会变成n个联通分量,即这n个城市都是不相连,这样从后往前每一条边的加入可能会改变联通分量的个数,这样的话用并查集从后往前每合并了一个城市,就使得当前的联通分量数--,记录下联通分量的个数,最后再倒着输出。
代码:
#include <stdio.h> const int N = 10005; const int M = 100005; int f[N], n, m, s[M][2], ans[M]; void init () { for (int i = 0; i < n; i++) f[i] = i; } int getfather(int x) { return x == f[x] ? x: f[x] = getfather (f[x]); } int main () { while (scanf ("%d%d", &n, &m) != EOF) { init (); int temp = n; for (int i = 0; i < m; i++) scanf ("%d%d", &s[i][0], &s[i][1]); ans[m] = n; for (int i = m - 1; i >= 0; i--) { int p = getfather (s[i][0]); int q = getfather (s[i][1]); if (q == p) ans[i] = temp; else { f[p] = q; ans[i] = --temp; } } for (int i = 1; i <= m; i++) printf ("%d\n", ans[i]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。