2 5 3 1 2 2 3 4 5 5 1 2 5Sample Output
2 4
题意：A 认识 B ， B 认识 C ， 则 A B C 可以坐在一张桌子上 ， 所有相互认识的人组成一个集合 一个集合的人坐一张桌子
问 需要准备多少张桌子 （有多少个集合）。
思路：并查集 模板题目。
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> using namespace std ; #define maxn 5000 int n , m ; int num1 , num2 ; int t ; int father[maxn] ; bool visit[maxn] ; void init(){ for(int i=1 ; i<=n ; i++){ father[i] = i ; } return; } int find(int x){ if(x!=father[x]){ father[x] = find(father[x]) ; } return father[x] ; } void Union_set(int x , int y){ int rootx = find(x) ; int rooty = find(y) ; if(rootx != rooty){ father[rooty] = rootx ; } return; } int check(){ memset(visit , false , sizeof(visit)) ; int result = 0 ; for(int i=1 ; i<=n ; i++){ visit[find(i)] = true ; } for(int i=1 ; i<=n ; i++){ if(visit[i]){ result ++ ; } } return result ; } int main(){ scanf("%d" , &t) ; while(t--){ scanf("%d %d" , &n , &m) ; init() ; for(int i=1 ; i<=m ; i++){ scanf("%d %d" , &num1 , &num2) ; Union_set(num1 , num2) ; } int result = check() ; printf("%d\n" , result) ; } return 0 ; }
kuangbin专题五：C - How Many Tables HDU - 1213
原文：http://www.cnblogs.com/yi-ye-zhi-qiu/p/8000616.html
