7
HDU1213 How Many Tables（并查集）
source link: https://arminli.com/hdu1213/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Armin's Blog
HDU1213 How Many Tables（并查集）
March 30, 2016
题意：n 个人，如果 a 和 b 认识，b 和 c 认识，那么认为 a b c 都互相认识，三个人被安排在一张桌子上，问这 n 个人最少安排多少张桌子。
并查集裸题。
#include<cstring>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int fa[1005];
int n, m, t;
int findfa(int x){
if(fa[x] != x){
fa[x] = findfa(fa[x]);
}
return fa[x];
}
void add(int x, int y){
if(x > y)
swap(x, y);
x = findfa(x);
y = findfa(y);
if(x != y){
fa[y] = x;
n--;
}
}
int main(){
// freopen("a.txt", "r", stdin);
cin >> t;
while(t--){
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++)
fa[i] = i;
while(m--){
int a, b;
scanf("%d %d", &a, &b);
add(a, b);
}
cout << n << endl;
}
return 0;
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK