1118 Birds in Forest
发布时间:2020-12-14 03:47:13 所属栏目:大数据 来源:网络整理
导读:题意: 思路:并查集模板题。 代码: #include cstdio #include algorithm using namespace std; const int maxn= 10005 ; int father[maxn]; int birdSet[maxn]={ 0 }; void Init(){ for ( int i= 1 ;imaxn;i++ ) father[i] = i;} int FindSet( int a){ int
题意: 思路:并查集模板题。 代码: #include <cstdio> #include <algorithm> using namespace std; const int maxn=10005; int father[maxn]; int birdSet[maxn]={0}; void Init() { for(int i=1;i<maxn;i++) father[i]=i; } int FindSet(int a) { int root=a; while(father[root]!=root) root=father[root]; //剪枝,(不剪枝会超时哦) while(father[a]!=a){ int tmp=a; a=father[a]; father[tmp]=root; } return root; } void Union(int a,int b) { int seta=FindSet(a); int setb=FindSet(b); if(seta!=setb) father[setb]=seta; } int main() { //freopen("pat.txt","r",stdin); Init(); int n,m,pre,curr; int birdCnt=0; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d%d",&m,&pre); if(pre>birdCnt) birdCnt=pre; for(int j=1;j<m;j++){ scanf("%d",&curr); if(curr>birdCnt) birdCnt=curr; Union(pre,curr); pre=curr; } } for(int i=1;i<=birdCnt;i++) birdSet[FindSet(i)]++; int setCnt=0; for(int i=1;i<=birdCnt;i++) if(birdSet[i]!=0) setCnt++; printf("%d %dn",setCnt,birdCnt); int query,a,b; scanf("%d",&query); for(int i=0;i<query;i++){ scanf("%d%d",&a,&b); if(FindSet(a)==FindSet(b)) printf("Yesn"); else printf("Non"); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |