题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=3560题意：求连通分量的个数和环图的个数。如果是环图那么每个点的度数应该为2。
#include<iostream>
using namespace std;
typedef struct
{
int v;
int next;
}edge;
edge e[600005];
int head[100005];
int deg[100005];
bool vis[100005];
int n,m,num1,num2;
void bfs(int u)
{
num1++;
vis[u]=1;
bool flag=0;
int front=0,rear=0;
int q[100005];
q[rear++]=u;
if(deg[u]!=2) flag=1;
while(front<rear)
{
int x=q[front++];
for(int i=head[x];i!=-1;i=e[i].next)
{
if(!vis[e[i].v])
{
vis[e[i].v]=1;
if(deg[e[i].v]!=2) flag=1;
q[rear++]=e[i].v;
}
}
}
if(!flag) num2++;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF&&(n||m))
{
int i,j,uu,vv,tot=0;
memset(head,-1,sizeof(head));
memset(deg,0,sizeof(deg));
memset(vis,0,sizeof(vis));
for(i=0;i<m;i++)
{
scanf("%d%d",&uu,&vv);
deg[uu]++;
deg[vv]++;
e[tot].v=vv;
e[tot].next=head[uu];
head[uu]=tot++;
e[tot].v=uu;
e[tot].next=head[vv];
head[vv]=tot++;
}
num1=0,num2=0;
for(i=0;i<n;i++)
if(!vis[i])
bfs(i);
printf("%d %d\n",num1,num2);
}
//system("pause");
return 0;
}
posted on 2010-08-25 18:55
wuxu 阅读(369)
评论(2) 编辑 收藏 引用 所属分类:
图论