J - 小希的迷宫 https://vjudge.net/problem/HDU-1272 HDU - 1272 https://vjudge.net/problem/11138/origin
- #include <iostream>
- #include <cstring>
- #include <queue>
- #include <set>
- using namespace std;
- const int maxn=1e5+5;
- int x;
- int f[maxn];
- int find(int x){
- if(x!=f[x]){
- f[x]=find(f[x]);
- }
- return f[x];
- }
- void init(){
- for(int i=0;i<=100000;i++)
- f[i]=i;
- }
- set<int> S;
- int main(){
- int a,b;int flag=1;
- std::iOS::sync_with_stdio(false);
- init();
- while(cin>>a>>b){
- if(a==-1&&b==-1) break;
- if(a==0&&b==0)
- {
- //cout <<"flag="<<flag<<endl;
- //cout <<"S.ize"<<S.size()<<endl;
- if(flag==0)
- {
- cout <<"No\n";
- flag=1;
- continue;
- }
- else
- {
- //cout <<"in";
- int sign;set<int>::iterator it=S.begin();
- if(!S.empty()) sign=find(*it),it++;
- for(;it!=S.end();it++){
- if(find(*it)!=sign) flag=0;
- //cout <<"in";
- }
- if(flag) cout <<"Yes\n";
- else cout <<"No\n";
- }
- //cout <<"in";
- flag=1;
- S.clear();
- init();
- }
- else
- {
- S.insert(a);S.insert(b);
- int fa=find(a);
- int fb=find(b);
- //cout <<"root"<<fa<<" "<<fb<<endl;
- if(fa==fb)
- {
- flag=0;
- }else
- {
- f[fb]=fa;
- }
- }
- }
- return 0;
- }
因为分到了并查集专题, 就直接想到用并查集.
如果要连的当前边的两个端点在之前的图中已经连通, 那么当前边一定会与之前的图构成一个环, 那么直接就不成立了. 如果没有环, 那么再判断是否连通, 如果连通就成立. 算是一道并查集的应用题.
来源: http://www.bubuko.com/infodetail-3137545.html