1118 Birds in Forest (25分)

题目大意：给定n张照片，每张照片中有k只鸟在同一棵树上，再给出几对鸟，判断它们是否在同一棵树上。

典型的并查集问题！不懂可以看中国大学mooc上浙江大学的《数据结构》课程（在树（下），讲的很好，也有代码讲解和完整的代码实现）

#include<iostream>                  //输入输出流头文件
#include<vector>                    //变长数组容器
using namespace std;                //标准命名空间
int n,m,k,x,y,maxnumber=0,flag=0,treenum=0;
int s[10001]={0};
int findset(int s[],int e);
void unionset(int s[],int e1,int e2);
int main(){                         //主函数cin>>n;vector<int> v;for(int i=0;i<n;i++){cin>>m;v.clear();flag=0;for(int j=0;j<m;j++){cin>>x;v.push_back(x);if(x>maxnumber) maxnumber=x;if(s[x]==0) s[x]=-1;else flag=x;}if(flag==0) flag=v[0];for(int j=0;j<m;j++){if(v[j]!=flag) unionset(s,flag,v[j]);}}for(int i=1;i<=maxnumber;i++){if(s[i]<0)  treenum++;}cout<<treenum<<' '<<maxnumber<<endl;cin>>k;for(int i=0;i<k;i++){cin>>x>>y;int r1=findset(s,x);int r2=findset(s,y);if(r1==r2)cout<<"Yes"<<endl;//如果根结点相同else cout<<"No"<<endl;}return 0;                       //返回0，如果不返回0，PAT会报错
}
int findset(int s[],int e){//寻找根if(s[e]<0) return e;else return s[e]=findset(s,s[e]);
}
void unionset(int s[],int e1,int e2){//合并int root1=findset(s,e1);int root2=findset(s,e2);if(root1!=root2) {if(root1<root2) {s[root2]+=s[root1];s[root1]=root2;}else {s[root1]+=s[root2];s[root2]=root1;}}
}