題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1213


Problem Description Today is Ignatius' birthday. He invites a lot of friends. Now it's dinner time. Ignatius wants to know how many tables he needs at least. You have to notice that not all the friends know each other, and all the friends do not want to stay with strangers.

One important rule for this problem is that if I tell you A knows B, and B knows C, that means A, B, C know each other, so they can stay in one table.

For example: If I tell you A knows B, B knows C, and D knows E, so A, B, C can stay in one table, and D, E have to stay in the other one. So Ignatius needs 2 tables at least.

Input The input starts with an integer T(1<=T<=25) which indicate the number of test cases. Then T test cases follow. Each test case starts with two integers N and M(1<=N,M<=1000). N indicates the number of friends, the friends are marked from 1 to N. Then M lines follow. Each line consists of two integers A and B(A!=B), that means friend A and friend B know each other. There will be a blank line between two cases.

Output For each test case, just output how many tables Ignatius needs at least. Do NOT print any blanks.

Sample Input 2 5 3 1 2 2 3 4 55 1 2 5
Sample Output 2 4

將問題抽象出來就是并查集，就是要求進行若干次merge操作之后，還會剩下多少顆樹， 這里說的樹指的是假設(shè)每個人都是一棵樹。擁有相同根樹的人將樹減一 （--count）。其實，這也是社交網(wǎng)絡(luò)中的最基本的功能，每次系統(tǒng)向你推薦的那些好友一般而言，會跟你在一個“圈子”里面，換言之，也就是你可能認(rèn)識的人，以并查集的視角來看這層關(guān)系，就是你們掛在同一顆樹上。

如下代碼：

#include<iostream> #include<cstdio> #include<cstring> #define M 1000+5 using namespace std;int root[M],sz[M]; int count;int find(int p){while(p!=root[p]){root[p]=root[root[p]];/*路徑壓縮，會破壞掉當(dāng)前節(jié)點的父節(jié)點的尺寸信息，因為壓縮后，當(dāng)前節(jié)點的父節(jié)點已經(jīng)變了 */ p=root[p];}return p; }void merge(int p, int q){int pRoot=find(p);int qRoot=find(q);if(pRoot == qRoot ) return ;if(sz[pRoot]<sz[qRoot]){// 按秩進行合并，將子樹小的掛在子樹大的上邊 root[pRoot]=qRoot;sz[qRoot]+=sz[pRoot];}else{root[qRoot]=pRoot;sz[pRoot]+=sz[qRoot];}--count; // 每次合并之后，樹的數(shù)量減1 }int main(){int t;scanf("%d",&t);while(t--){int n;scanf("%d%d", &count, &n);for(int i=1; i<=count; ++i){root[i]=i;sz[i]=1;}for(int i=0; i<n; ++i){int a,b;scanf("%d%d", &a, &b);merge(a, b);}printf("%d\n",count);}return 0; }

參考資料：http://blog.csdn.net/dm_vincent/article/details/7655764

參考資料：http://blog.csdn.net/dm_vincent/article/details/7769159

總結(jié)

以上是生活随笔為你收集整理的HD 1213 How Many Tables(裸 并查集）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。