题目链接:hdu 4496 D-City
题目大意:给出一张图,按照给定边的顺序逐个删除,问没删除一条之后的联通块数量。
解题思路:逆向并查集求联通分量,假设一开始各个城市都不连通,然后从最后一条边开始添加,如果新添加的边联通了两个联通块,那么联通分量就要减1,最后在正序输出即可。
#include <cstdio>
#include <cstring>
const int N = 10005;
const int M = 100005;
int n, m, ans[M];
int f[N], x[M], y[M];
int getfar(int s) {
return s == f[s] ? s : f[s] = getfar(f[s]);
}
void init () {
for (int i = 0; i < n; i++)
f[i] = i;
for (int i = 0; i < m; i++)
scanf("%d%d", &x[i], &y[i]);
}
void solve () {
int tmp = n;
for (int i = m - 1; i >= 0; i--) {
ans[i] = tmp;
int p = getfar(x[i]);
int q = getfar(y[i]);
if (p != q) {
f[q] = p;
tmp--;
}
}
for (int i = 0; i < m; i++)
printf("%d\n", ans[i]);
}
int main () {
while (scanf("%d%d", &n, &m) == 2) {
init();
solve();
}
return 0;
}
分享到:
相关推荐
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
ACM题库,一些题目和答案,以及解题报告,传上来共享
杭州电子科技大学ACM Steps中Chapter One-Section One的答案集。不要直接抄哦~~ 如需题解请上我的博客~ 博客地址呈上:http://blog.csdn.net/xu_zh
杭州电子科技大学ACM Steps中Chapter One-Section Two的答案集。不要直接抄哦~~ 如需题解请上我的博客~ 博客地址呈上:http://blog.csdn.net/xu_zh
杭电OnlineJudge 200-2099的解题报告
HDU 里面的2000~2099道题目的源码。谢谢支持
杭电ACM课件2014版之 (HDUACM201403版_06)并查集(最小生成树)
可拆卸核心板滤波电容电源指示灯排针复位F103--R10不焊F207--R9不焊第19引脚F103--C4焊0欧姆,C3不焊Tuesday, August 31
杭电ACM2000-2099题的解题报告
排母,核心板接口ADC 电位器扩展接口,预留模拟量Tuesday, August 31, 2021Tuesday, August 31, 2021Tuesday
(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树
求多源点到单终点的最短路(反向建图),ACM竞赛中应用的小程序。
基础算法类 ACM 入门 杭电OJ 11页题目题解,算法入门的时候刷题可以参考 搜集整理起来了比单个去搜题解方便快捷
示例 1:输出:[1,2,3,7,8,11,12,9,10,4,5,6]输入的多级列表如下图所示:扁平化后的链表如下图:示例 2:输出:[1,3,2]解释:输入
其中一类查询要求 更新 数组 nums 下标对应的值另一类查询要求返回数组 nums 中索引 left 和索引 right 之间( 包含 )的nums元素的 和
示例 1:示例 2:解答:大小写转换: n = n ^ 32转小写: n = n | 32转大写: n = n & -33const toLowerCase =
2016. 增量元素之间的最大差值题目描述:给你一个下标从 0 开始的整数数组 nums ,该数组的大小为 n ,请你计算 nums[j] - nums[i]