正題

---

大意

有n個犯罪團伙，他們之間可以相互聯系，按照1到n的順序打擊，求最少打擊多少個犯罪團伙可以使多個犯罪團伙組成的已經無法與外聯系的團伙最大的那個不超過n/2。

---

解題思路

先儲存每條連接的路徑，然后從n枚舉到1，連接它擴展出去的邊，直到最大的那個大于n/2就好了

---

代碼

#include<cstdio> using namespace std; int k,l[1001][1001],n,father[1001],lt[1001]; bool flag,v[1001]; int find(int x) {if (father[x]!=x) return father[x]=find(father[x]);return father[x]; } void unionn(int x,int y) {int fa=find(x),fb=find(y);if (fa==fb || !v[x] || !v[y]) return;if (fa<fb){ father[fb]=fa;lt[fa]+=lt[fb];//計算個數}else{father[fa]=fb;lt[fb]+=lt[fa];} } int main() {scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%d",&l[i][0]);for (int j=1;j<=l[i][0];j++){scanf("%d",&l[i][j]);}lt[i]=1;father[i]=i;v[i]=false;}for (int i=n;i>=1;i--){v[i]=true;//設置為可以聯通for (int j=1;j<=l[i][0];j++){unionn(i,l[i][j]);//向外擴張}flag=true;for (int j=1;j<=n;j++){if (lt[j]>n/2) flag=false;}if (!flag)//已經大于{k=i;break;}}printf("%d",k); }

總結

以上是生活随笔為你收集整理的ssl2342-打击犯罪【并查集】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。