勵志用少的代碼做高效表達
分析與思路
n個人吃飯，只能熟人和熟人坐在一起，否則就一個人坐一桌， 給定m個關系(m對熟人)，問最少需要多少張桌子，
純粹考查的并查集模板的題， 給定m個關系就代表了m個集合， 將有相同元素的集合和并， 最后計算集合的個數即可，
視頻講解——>傳送門
這里分享一下我學習新演算法的方法：
- 通過觀看視頻或檔案(最好是視頻)理解基礎的原理
- 嘗試理解代碼
- 手寫代碼，一面回想原理一面默寫， 一般默寫一到兩遍就記牢了(千萬不要只用電腦敲，忘得超快， 好記性不如爛筆頭)，
- 不停的刷型別題， 一般刷完8-10道題，就可以比較熟練的運用這一類演算法，
#include<bits/stdc++.h>
using namespace std;
int per[1010];
int find(int x) {
if(x==per[x]) return x;
per[x] = find(per[x]);
return per[x];
}
void Union(int a, int b) { //建立并集
int t1 = find(a);
int t2 = find(b);
if(t1 != t2) per[t1] = t2;
}
int main() {
ios::sync_with_stdio(false);
int T; cin>>T; while(T--) {
int n, m; cin>>n>>m;
for(int i = 1; i <= n; i++) per[i] = i;
while(m--) {
int a, b; cin>>a>>b;
Union(a, b); //對所有序對建立并
}
int ans = n;
for(int i = 1; i <= n; i++) if(per[i] != i) ans--;
cout << ans << endl;
}
return 0; }
如果這篇文章對你產生了幫助，就請給博主一個贊吧！讓更多的人看到它，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/87728.html
標籤：其他
上一篇：Android 物件池的簡單實作