Link
T399752 The Maze of the Imperial Sister(御姐的迷宫)
Question
判断图内是否有环
Solution
先判断连通性,所有点是不是在一个块内,然后用树的性质,点数 \(=\) 边数 \(+1\) 判断
Code
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5,maxe=maxn*2;
struct IO{
static const int S=1<<21;
char buf[S],*p1,*p2;int st[105],Top;
~IO(){clear();}
inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}
inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline IO&operator >> (char&x){while(x=gc(),x==' '||x=='\n'||x=='r');return *this;}
template<typename T>inline IO&operator >> (T&x){
x=0;bool f=0;char ch=gc();
while(ch<'0'||ch>'9'){if(ch=='-') f^=1;ch=gc();}
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=gc();
f?x=-x:0;return *this;
}
inline IO&operator << (const char c){pc(c);return *this;}
template<typename T>inline IO&operator << (T x){
if(x<0) pc('-'),x=-x;
do{st[++st[0]]=x%10,x/=10;}while(x);
while(st[0]) pc('0'+st[st[0]--]);return *this;
}
}fin,fout;
struct node{
int x,y;
};
vector<node> Q;
int M,N;
vector<int> a;
int vis[maxn],num_m[maxn],num_n[maxn];
int fa[maxn];
int getfa(int x){
return fa[x]==x?x:fa[x]=getfa(fa[x]);
}
int main(){
freopen("C.in","r",stdin);
// freopen("C.out","w",stdout);
while(1){
while(1){
int x,y;fin>>x>>y;
if(x==-1&&y==-1) return 0;
else if(x==0&&y==0) break;
M++;
node now;
now.x=x,now.y=y;
Q.push_back(now);
if(!vis[x]) a.push_back(x),vis[x]=1;
if(!vis[y]) a.push_back(y),vis[y]=1;
}
int N=a.size();
for(int i=0;i<N;i++) fa[a[i]]=a[i];
for(int i=0;i<M;i++){
int fx=getfa(Q[i].x),fy=getfa(Q[i].y);
if(fx==fy)continue;
fa[fx]=fy;
}
for(int i=0;i<N;i++){
int fa=getfa(a[i]);
num_n[fa]++;
}
for(int i=0;i<M;i++){
int fa=getfa(Q[i].x);
num_m[fa]++;
}
int F=getfa(a[0]);
if(num_n[F]==N&&num_m[F]==N-1) printf("Yes\n");
else printf("No\n");
for(int i=0;i<N;i++) vis[a[i]]=0,fa[a[i]]=0,num_n[a[i]]=0,num_m[a[i]]=0;
N=M=0;
a.clear();Q.clear();
}
return 0;
}
标签:T399752,ch,fa,int,题解,Sister,vis,while,maxn
From: https://www.cnblogs.com/martian148/p/17840255.html