点击打开链接uva 11987
思路: 并查集
分析:
1 题目给定三种操作,符合并查集的模式
2 但是有一种操作和普通的并查集不同的是,2 p q要把p并到q的集合,那么这个时候p所在的集合就会发生变化,如果p刚好是它那个集合的跟节点那么这个时候就要重新调整这个集合
3 那么我们为了避免这种删除跟节点的情况出现,我们就把所有的i~n的节点的跟节点指向i+n,这样保证了删除的时候肯定不会是根节点。这样就变成了简单的并查集问题了
代码:
#include<cstdio>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 100010;
int n , m;
int father[MAXN];
int sum[MAXN] , num[MAXN];
void init(){
for(int i = 1 ; i <= n ; i++){
father[i] = i+n;
father[i+n] = i+n;
sum[i+n] = i;
num[i+n] = 1;
}
}
int find(int x){
if(father[x] != x)
father[x] = find(father[x]);
return father[x];
}
int main(){
int mark , x , y;
while(scanf("%d%d" , &n , &m) != EOF){
init();
for(int i = 0 ; i < m ; i++){
scanf("%d" , &mark);
if(mark == 1){
scanf("%d%d" , &x , &y);
int fx = find(x);
int fy = find(y);
if(fx != fy){
father[fx] = fy;
sum[fy] += sum[fx];
num[fy] += num[fx];
}
}
else if(mark == 2){
scanf("%d%d" , &x , &y);
int fx = find(x);
int fy = find(y);
if(fx != fy){
father[x] = fy;
sum[fy] += x;
sum[fx] -= x;
num[fy] ++;
num[fx] --;
}
}
else{
scanf("%d" , &x);
int fx = find(x);
printf("%d %d\n" , num[fx] , sum[fx]);
}
}
}
return 0;
}
分享到:
相关推荐
开源项目-codingsince1985-UVa#uva-online-judge-solutions-in-golang.zip,两年来每天都在解决一个uva在线裁判问题,算起来…
uva705 Slash Maze 的代码,在UVaOJ上通过
uva532 Dungeon Master的源代码,并且AC了
Algorithm-UVA-Solutions-in-Python.zip,python 3中各种uva(acm)问题的解决方案。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
52道题 ,题目太多,就不一一写出来了,绝对实用
UVa-online-judge:针对在http://uva.onlinejudge.org上发现的一些问题的解决方案的集合
uva-infovis-group-12
leetcode 2 算法-Java UVa Online Judge(ACM-ICPC Live ...使用:数组、哈希表、链表、二分搜索、动态规划、堆栈、堆、reedy、排序、树 DFS、BFS、图、二分搜索树、递归、记忆、队列、映射等。...Uva-ACM-ICPC
[UVa在线评审工具]此工具可帮助您快速访问现场评审,提交,快速提交表格和问题详细信息 这是UVa在线法官的一个小工具-http://uva.onlinejudge.org/。 只需单击一次,就无需打开新选项卡,您可以:1.将问题解决方案...