基礎的 Disjoint sets。
沒什麼特別的,就是要注意可能會有環,遇到環忽略他就好,然後要記得是大連到小。
參考:http://mikucode.blogspot.com/2014/03/step5problem-0118.html
#include <iostream>
#define F(n) Fi(i,n)
#define Fi(i,n) for(int i=0;i<n;i++)
#define N 10001
using namespace std;
int F[N];
int find(int x){
if(F[x]==x)return x;
return F[x]=find(F[x]);
}
main(){
int n,m,a,b,k;
while(cin>>n>>m){
F(n)F[i+1]=i+1;
F(m){
cin>>a>>b;
if(find(a)==find(b))continue;
if(find(a)>find(b))k=a,a=b,b=k;
F[find(b)]=find(a);
}
cin>>k;
cout<<find(k)<<endl;
}
}
沒有留言:
張貼留言