HDU 3560 并查集 Graph’s Cycle Component

分析: 这题另外还要求简单环的个数, 只要加一个标记数组将不是简单环的集合标记即可.

[cpp]
#include
#include
#include
#include
#include
#include
#include

using namespace std;
const int maxn=100000;
int f[maxn];
int ds[maxn];
bool vis[maxn];

int find_set(int x){
if(f[x]!=x)f[x]=find_set(f[x]);
return f[x];
}
void union_set(int x,int y){
x=find_set(x);
y=find_set(y);
if(x!=y)f[y]=x;
}
int main() {
int n,m;
while(~scanf("%d%d",&n,&m),n||m){
memset(ds,0,sizeof(ds));
memset(vis,true,sizeof(vis));
for(int i=0;i while(m--){
int a,b; scanf("%d%d",&a,&b);
ds[a]++; ds[b]++;
union_set(a,b);
}
for(int i=0;i if(ds[i]!=2) vis[find_set(i)]=false;
int s=0,h=0;
for(int i=0;i if(find_set(i)==i){
s++;
if(vis[i])h++;
}
printf("%d %d\n",s,h);
}
return 0;
}

#include
#include
#include
#include
#include
#include
#include

using namespace std;
const int maxn=100000;
int f[maxn];
int ds[maxn];
bool vis[maxn];

int find_set(int x){
if(f[x]!=x)f[x]=find_set(f[x]);
return f[x];
}
void union_set(int x,int y){
x=find_set(x);
y=find_set(y);
if(x!=y)f[y]=x;
}
int main() {
int n,m;
while(~scanf("%d%d",&n,&m),n||m){
memset(ds,0,sizeof(ds));
memset(vis,true,sizeof(vis));
for(int i=0;i while(m--){
int a,b; scanf("%d%d",&a,&b);
ds[a]++; ds[b]++;
union_set(a,b);
}
for(int i=0;i if(ds[i]!=2) vis[find_set(i)]=false;
int s=0,h=0;
for(int i=0;i if(find_set(i)==i){
s++;
if(vis[i])h++;
}
printf("%d %d\n",s,h);
}
return 0;
}