P1714【Week4】島嶼

時間限制 : 10000 MS?? 空間限制 : 128000 KB

問題描述

湖面上有 n 座島嶼，從1~n 編號。現在要湖上建橋使得島嶼連接起來。橋雙向通行。

輸入格式

輸入第一行有兩個整數 n,m。
接下來是 m 行，按照時間順序每行是一次詢問。
每行第一個整數q 代表詢問的內容：
如果q=1，則接下來是兩個島嶼編號a,b(a≠b)；
如果q=2，則接下來是一個島嶼編號c。

輸出格式

對于每個詢問，按次序各輸出一行作為回答：
q=1 時：如果a,b 相互可達，則輸出Yes；如果a,b 相互不可達，則輸出No，并在a,b之間建一座橋。
q=2 時：輸出一個整數x，表示由c 出發可以到達的島嶼有x 個（不包括c 自身）。

樣例輸入

5?9
1?2?3
1?3?2
2?1
2?2
1?4?5
1?2?4
1?2?5
2?4
2?5

樣例輸出

No
Yes
0
1
No
No
Yes
3
3

提示

對于 100%的數據，2≤n≤10,000, 1≤m≤30,000。

問題分析： 問題1：查詢a,b兩個元素是否位于同一個集合，若不是，將兩個集合合并。 問題2：詢問元素c所在集合的元素的個數。 合并時 集合個數相加 code: // #include<bits/stdc++.h> using namespace std; #define maxnn 30100 int f[maxnn],cnt[maxnn]; int q; int n,m; int gf(int v) {return f[v]==v? v: f[v]=gf(f[v]); } void merge(int x,int y) {int fx=gf(x);int fy=gf(y);if(fx!=fy){f[fx]=fy;cnt[fy]+=cnt[fx];} } int main() {cin>>n>>m;int x,y;for(int i=1;i<=n;i++)f[i]=i,cnt[i]=1;for(int i=1;i<=m;i++){cin>>q;if(q==1){cin>>x>>y;if(gf(x)==gf(y))cout<<"Yes"<<endl;elsecout<<"No"<<endl;if(!(gf(x)==gf(y)))merge(x,y);}else{cin>>x;cout<<cnt[gf(x)]-1<<endl;}}}

?

轉載于:https://www.cnblogs.com/OIEREDSION/p/11260121.html

總結

以上是生活随笔為你收集整理的岛屿(并查集)的全部內容，希望文章能夠幫你解決所遇到的問題。

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