最小边覆盖

Wannafly Day 3 C

题目来源：comet OJ

分析

题目给出了一个图，要求判断该图能否有可能是某一个图的最小边覆盖。

那么，我们需要考虑的便是最小边覆盖的性质：所有点必须连边；边最少。那么，实际上整个图一定可以分成许多不连通的子图，并且它们只会存在两种情况：一条边连两个点；菊花状的\(n\)条边连接\(n+1\)个点。也就是说，不会有两个度数大于2的点相连，并且点的度数不能为\(0\)。

代码

#include <iostream>

using namespace std;
int a[300010],b[300010];
int h[200010];
bool res=1;

int main()
{
    int m,n;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        cin>>a[i]>>b[i];
        h[a[i]]++;
        h[b[i]]++;
    }
    for(int i=0;i<m;i++)
        if(h[a[i]]>=2 && h[b[i]]>=2)
            res=0;
            
    for(int i=1;i<=n;i++)
        if (!h[i])
            res = false;
    if(res)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。