題意
給你一些不同顏色的襪子，你要把它們放到一個容器中配對，如果能使所有的襪子配對成功，問這個容器最小的容量是多少，
解題思路
用并查集進行配對，把每雙有相同顏色的襪子都放在一個集合，因為編號較大需要用map代替陣列來存，這里注意用普通map存因為查詢次數過多會超時，所以用hashmap來代替，另外dfs也可以做
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100050;
unordered_map <int,int> f, p;
int ans;
int n, m;
struct node {
int x, y;
}q[MAXN];
int find(int x){
if(f[x]==x)return x;
else return f[x]=find(f[x]);
}
int main(){
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t --){
cin >> n;
f.clear(), p.clear();
for (int i = 1; i <= n; i++) cin >> q[i].x >> q[i].y, f[q[i].x] = q[i].x, f[q[i].y] = q[i].y;
for (int i = 1; i <= n; i++){
int a, b;
a = q[i].x, b = q[i].y;
if (find(a) != find(b)) f[find(b)] = f[find(a)];
}
for (int i = 1; i <= n; i++){
p[find(q[i].x)] += 2;
ans = max(ans, p[find(q[i].x)]);
}
cout << ans / 2 << endl;
ans = 0;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/278583.html
標籤：其他