【海岛帝国系列赛】No.2 海岛帝国：“落汤鸡”市的黑帮危机

50200210海岛帝国：“落汤鸡”市的黑帮危机

【试题描述】

近几天，犯罪分子发现“药师傅”帝国的警力约等于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

【输出实例】

【其他说明】

无

【试题分析】

一看到什么团伙，什么信息这样的词，就一定知道要用神奇的“并查集”了。那我们先来看看：什么是并查集吧！

1. 简述

    并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。
    需要实现的操作有：合并两个集合，判断两个元素是否属于一个集合。
    这里介绍的主要是普通的并查集，很多情况下使用的并查集是需要扩展的，根据使用情况的不同，有很多差别，这里仅仅是最基本的算法。

经典的find函数：

int findset(int x)    
{    
    if(pa[x] != x)    
    {           
        int root = findset(pa[x]);     
        return pa[x] = root;    
    }    
    else    
    {    
        return x;    
    }    
}

初始化：

void init()     //初始化   该函数可以根据具体情况保存和初始化需要的内容    
{    
    for(int i = 0; i < MAX_SIZE; i++)    
    {    
        pa[i] = i;    
    }   
}

1、Make_Set(x) 把每一个元素初始化为一个集合

初始化后每一个元素的父亲节点是它本身，每一个元素的祖先节点也是它本身（也可以根据情况而变）。

2、Find_Set(x) 查找一个元素所在的集合

查找一个元素所在的集合，其精髓是找到这个元素所在集合的祖先！这个才是并查集判断和合并的最终依据。
判断两个元素是否属于同一集合，只要看他们所在集合的祖先是否相同即可。
合并两个集合，也是使一个集合的祖先成为另一个集合的祖先，具体见示意图

3、Union(x,y) 合并x,y所在的两个集合

合并两个不相交集合操作很简单：
利用Find_Set找到其中两个集合的祖先，将一个集合的祖先指向另一个集合的祖先。如图

并查集的优化

1、Find_Set(x)时路径压缩
寻找祖先时我们一般采用递归查找，但是当元素很多亦或是整棵树变为一条链时，每次Find_Set(x)都是O(n)的复杂度，有没有办法减小这个复杂度呢？
答案是肯定的，这就是路径压缩，即当我们经过"递推"找到祖先节点后，"回溯"的时候顺便将它的子孙节点都直接指向祖先，这样以后再次Find_Set(x)时复杂度就变成O(1)了，如下图所示；可见，路径压缩方便了以后的查找。

2、Union(x,y)时按秩合并
即合并的时候将元素少的集合合并到元素多的集合中，这样合并之后树的高度会相对较小。

1int father[MAX];   /* father[x]表示x的父节点*/
2int rank[MAX];     /* rank[x]表示x的秩*/
3
4
5/* 初始化集合*/
6void Make_Set(int x)
7{
8    father[x] = x; //根据实际情况指定的父节点可变化
9    rank[x] = 0;   //根据实际情况初始化秩也有所变化
10}
11
12
13/* 查找x元素所在的集合,回溯时压缩路径*/
14int Find_Set(int x)
15{
16    if (x != father[x])
17    {
18        father[x] = Find_Set(father[x]); //这个回溯时的压缩路径是精华
19    }
20    return father[x];
21}
22
23
24/*
25   按秩合并x,y所在的集合
26   下面的那个if else结构不是绝对的，具体根据情况变化
27   但是，宗旨是不变的即，按秩合并，实时更新秩。
28*/
29void Union(int x, int y)
30{
31    x = Find_Set(x);
32    y = Find_Set(y);
33    if (x == y) return;
34    if (rank[x] > rank[y])
35    {
36        father[y] = x;
37    }
38    else
39    {
40        if (rank[x] == rank[y])
41        {
42            rank[y]++;
43        }
44        father[x] = y;
45    }
46}
47

并且传说中的并查集按秩合并：

 1 const int MAXSIZE = 500;
 2 int uset[MAXSIZE];
 3 int rank[MAXSIZE];
 4  
 5 void makeSet(int size) {
 6     for(int i = 0;i < size;i++)  uset[i] = i;
 7     for(int i = 0;i < size;i++)  rank[i] = 0;
 8 }
 9 int find(int x) {
10     if (x != uset[x]) uset[x] = find(uset[x]);
11     return uset[x];
12 }
13 void unionSet(int x, int y) {
14     if ((x = find(x)) == (y = find(y))) return;
15     if (rank[x] > rank[y]) uset[y] = x;
16     else {
17         uset[x] = y;
18         if (rank[x] == rank[y]) rank[y]++;
19     }
20 }

这题只是并查集的基础，用到了find和merge合并

剩下的就貌似只有sum++了

【代码】

 1 #include<iostream>
 2 using namespace std;
 3 int f[50]={0},n,m,k,sum=0;
 4 void init()
 5 {
 6      int i;
 7      for(i=1;i<=n;i++) f[i]=i;
 8      return ;
 9 }
10 int getf(int v)
11 {
12     if(f[v]==v) return v;
13     else
14     {
15         f[v]=getf(f[v]);
16         return f[v];
17     }
18 }
19 void merge(int v,int u)
20 {
21      int t1,t2;
22      t1=getf(v);
23      t2=getf(u);
24      if(t1!=t2) f[t2]=t1;
25      return ;
26 }
27 int main()
28 {
29     int i,x,y;
30     scanf("%d%d",&n,&m);
31     init();
32     for(i=1;i<=m;i++)
33     {
34         scanf("%d%d",&x,&y);
35         merge(x,y);
36     } 
37     for(i=1;i<=n;i++)
38         if(f[i]==i) sum++;
39     printf("%d\n",sum);
40 }

View Code

【海岛帝国系列赛】No.2 海岛帝国：“落汤鸡”市的黑帮危机

推荐阅读