The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

浙大校赛 I 用了并查集

题意严重不明,开始还以为是顶点按顺序形成环,WA了N次之后改了算法才过的。。。

#include<iostream>
#include
<algorithm>
#include
<cstdio>
using namespace std;


int n,m;
int v[100][100];
int d[100];

int f[1000];
int r[1000];
int find(int n)
{
    
if(f[n]==n)
        
return n;
    
else
        f[n]
=find(f[n]);
    
return f[n];
}



int Union(int x,int y)
{
    
int a=find(x);
    
int b=find(y);
    
if(a==b)
        
return 0;
    
else if(r[a]<=r[b])
    
{
        f[a]
=b;
        r[b]
+=r[a];
    }

    
else
    
{
        f[b]
=a;
        r[a]
+=r[b];
    }

    
return 1;

}


int main()
{

    
while(scanf("%d%d",&n,&m)!=EOF)
    
{

        
int flag=0;
        memset(d,
0,sizeof(d));
        
int i,j;
        
for(i=0;i<n;i++)
        
{

            f[i]
=i;
            r[i]
=1;
        }

        
for(i=1;i<=m;i++)
        
{
            
int a,b;
            scanf(
"%d%d",&a,&b);
            Union(a,b);
            d[a]
++;
            d[b]
++;
        }

        
int tt=find(1);
        
if(r[tt]!=n)
        
{

            printf(
"NO\n");
            
continue;
        }


        
if(n!=m||n<3)
        
{
            printf(
"NO\n");
            
continue;
        }

        
for(i=1;i<=n;i++)
        
{

            
if(d[i]!=2)
            
{
                flag
=1;
                
break;
            }

        }

        
if(flag)
            printf(
"NO\n");
        
else
            printf(
"YES\n");

    }

    
return 0;
}

posted on 2010-04-10 18:14 abilitytao 阅读(982) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理