并查集 黑帮危机

试题描述     近几天，犯罪分子发现“药师傅”帝国的警力约等于0。（请见YSF的海岛帝国）于是开始猖狂了起来。他们选择了依山靠水（农村？）的“落汤鸡”市。开始抢劫财务，一天内发生了5起抢劫案，9起爆炸案，3起枪击案，12起绑架案！搞得YSF夜不能寐，况且每天还有那么多“怪物”要处理。于是，所有的责任都落在了“落汤鸡”市可怜的市长LTJ上。犯罪分子在LTJ市有了好多好多个窝点。市民开始惊慌起来，背井离乡。“郭同学”TONY由于YSF没还债而拒绝伸出援手。这时，YSF的“购物券”WHT提出了一个建议：请大名鼎鼎的“李易峰”探长来化解危机。于是，没主见的YSF照办了。不过，由于犯罪团伙庞大，作案频繁，数量众多，LTJ调查不清楚有几个犯罪团伙。不过，LYF探长还是搜集到了一些线索。助理YSM提出：强盗的同伙的同伙也是同伙，只有没有关系的才各自为政。请你帮帮可怜的LTJ、YSF、LYF，编一个程序来告诉他们有几个独立的犯罪团伙。 输入 * 第一行n表示强盗的人数，m表示警方搜集到的m条线索 * 接下来m行，每行两个整数a，b表示强盗a，b是同伙 输出 * 一个数：表示有几个独立的犯罪团伙 输入示例 10 9 1 2 3 4 5 2 4 6 2 6 8 7 9 7 1 6 2 4 输出示例 3

 

#include <iostream> #include <cmath> #include <cstring> using namespace std; int f[10010],n,m; void chushi() { for(int i=1;i<=n;i++) f[i]=i; return; } int father(int x) { if(f[x]==x) return f[x]; else { f[x]=father(f[x]); return f[x]; } } void hebing(int tm,int zhh) { int ltj1,ltj2; ltj1=father(tm); ltj2=father(zhh); if(ltj1!=ltj2) { f[ltj2]=ltj1; } return; } int main() { int sum=0; scanf("%d%d",&n,&m); chushi(); for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); hebing(x,y); } for(int i=1;i<=n;i++) { if(f[i]==i) sum++; } printf("%d",sum); }

 

转载于:https://www.cnblogs.com/jason2003/p/6572398.html

相关资源：JAVA上百实例源码以及开源项目