随笔-68  评论-10  文章-0  trackbacks-0
题目链接: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 阅读(353) 评论(2)  编辑 收藏 引用 所属分类: 图论

评论:
# re: hdu3560 2010-08-31 00:26 | X10A
汗啊,我也用bfs貌似就没你的运气了。。。。。  回复  更多评论
  
# re: hdu3560 2010-10-10 15:19 | 神の舞
这个跟写法有很大关系  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理