hdu1272 小希的迷宫 hdu1856 More is better

本文主要是介绍hdu1272 小希的迷宫 hdu1856 More is better，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

之所以把这两题放一块看是因为寻找祖先结点是有区别的，不然一个爆栈，一个TLE

hdu1272 小希的迷宫

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int root[100001],foot[100001];
int find(int t){   //不能用递归寻找祖先借点，不然会爆栈，汗while(root[t]!=t)t=root[t];return root[t];
}
void check(int a,int b){foot[a]=foot[b]=1;int ra=find(a);int rb=find(b);if(ra!=rb)root[ra]=rb;
}
void reset(){   //初始化for(int i=1;i<=100000;i++)root[i]=i;memset(foot,0,sizeof(foot));
}
int main(){int i=1;bool flag=0;int a,b;int key=0;reset();while(scanf("%d%d",&a,&b)){   //输入的格式也很奇葩if(a==-1&&b==-1)break;if(a==0&&b==0){for(i=1;i<=100000;i++)if(root[i]==i&&foot[i]==1)   //foot[]==1代表输入文件中包含的点key++;if(key>1)flag=1;if(flag)printf("No\n");elseprintf("Yes\n");flag=0;key=0;reset();continue;}if(find(a)==find(b))flag=1;elsecheck(a,b);}return 0;
}

hdu1856 More is better

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int root[10000010],sign[10000010];
int find(int c){   //亲测若采用while()找祖先直接TLEif(root[c]!=c)root[c]=find(root[c]);return root[c];
}
void check(int a,int b){int ra=find(a);int rb=find(b);if(ra!=rb){root[ra]=rb;sign[rb]+=sign[ra];}
}
int main(){int m;int i;int b1,b2;while(scanf("%d",&m)!=EOF){for(i=1;i<=10000000;i++){root[i]=i;sign[i]=1;}for(i=1;i<=m;i++){scanf("%d%d",&b1,&b2);check(b1,b2);}int ans=0;for(i=1;i<=10000000;i++)if(sign[i]>ans)ans=sign[i];printf("%d\n",ans);}return 0;
}

我已经感觉到蛋疼了...

这篇关于hdu1272 小希的迷宫 hdu1856 More is better的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---