注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

东月之神

在单纯的观念里面,生命就容易变得比较深刻!

 
 
 

日志

 
 
关于我

别驻足,梦想要不停追逐,别认输,熬过黑暗才有日出,要记住,成功就在下一步,路很苦,汗水是最美的书!

网易考拉推荐

The Partition of A Graph  

2010-08-12 10:45:29|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Problem Description
Simple enough, you’ll be given a simple undirected graph with n vertexes and m edges, try to divide this graph fits the following requirements: All edges are divided into several groups; only two edges exist in every group, and this two edges have common vertex.
Your task is to figure out if such a partition exists.
 
Input
There are multiple test cases, for each test case:
The first line contains two integers n (0<n<=1000) and m represent the number of vertexes and edges.
The following m lines, each line contains two integers represent two endpoints of an edge.
The vertexes are numbered from 1 to n.
The input terminated when n=m=0.
 
Output
For each test case, output one line, if such a partition exists, print “Yes”, otherwise, print “No”.
 
Sample Input


3 3 1 2 1 3 2 3 3 2 1 2 1 3 0 0


 
Sample Output


No Yes


求图的每个连通分支的边数,然后再判断边数是否为偶数,若是偶数,则yes,否则就是no,图论知识没有学好,用了模板求连通分支。悲剧。。。

#include <cstdio>
#include <iostream>
using namespace std;
#include <cstring>
#include <algorithm>
#define MAXN 1001

int map[MAXN][MAXN];
bool hash[MAXN*2];
struct node
{
    int x, y, num;
}s[MAXN*2];

inline bool comp(node p1, node p2)
{
   return p1.num > p2.num;
}

int find_components(int n,int mat[][MAXN],int* id)
{
   int ret,k,i,j,m;
   for (k=0;k<n;id[k++]=0);
   for (ret=k=0;k<n;k++)
       if (!id[k])
           for (id[k]=-1,ret++,m=1;m;)
               for (m=i=0;i<n;i++)
                   if (id[i]==-1)
                       for (m++,id[i]=ret,j=0;j<n;j++)
                           if (!id[j]&&mat[i][j])
                               id[j]=-1;
   return ret;
}

int main()
{
    int n, m, i, j;
    while(scanf("%d%d", &n, &m) != EOF && n + m)
    {
        memset(map, false, sizeof(map));
        for(i = 0; i < m; i++)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            map[a-1][b-1] = map[b-1][a-1] = true;
            s[i].x = a - 1;
            s[i].y = b - 1;
            s[i].num = 0;
        }
        if(m % 2){printf("No\n"); continue;}
        int ans, id[MAXN];
        ans =  find_components(n, map, id);
        memset(hash, true, sizeof(hash));
        for(i = 1; i <= n; i++)
        {
            for(j = 0; j < m; j++)
            {
                if(hash[j] && (s[j].x == i || s[j].y == i))
                {
                    hash[j] = false;
                    s[j].num =  id[i];
                }
            }
        }
        sort(s, s + m, comp);
        ans = 1;
        int cnt = s[0].num, flag = 1;
        for(i = 1; i < m; i++)
        {
            if(cnt == s[i].num)
            {
                ++ans;
            }
            else if(cnt != s[i].num)
            {
               if(ans % 2 == 1)
               {
                  printf("No\n");
                  flag = 0;
                  break;
               }
               else
               {
                  cnt = s[i].num;
                  ans = 1;
               }
            }
        }
        if(flag)
        {
            if(ans % 2 == 0)    printf("Yes\n");
            else printf("No\n");
        }
    }
return 0;
}

  评论这张
 
阅读(111)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017