1 or 2

I. 1 or 2

依次遍历所有的点，对于遍历的当前点，选择所需的边，直到度数饱和。当遍历点的序号 大于n时，则证明该解法时是可行的。

但是要注意的时候，遍历之前需要将节点按照邻接表的大小进行排序，这样时间复杂度会低一点。

解法也算是暴力吧，只不过优化了一下。

// Created by CAD on 2020/7/14.
#include <bits/stdc++.h>

#define fi first
#define se second
#define pii pair<int,int>
using namespace std;

vector<pii> g[55];
int d[55],id[55],n,vis[105];
bool cmp(int a,int b){
    return g[a].size()<g[b].size();
}
bool dfs(int x){
    int p=id[x];
    if(x>n) return 1;
    if(!d[p]) return dfs(x+1);
    for(auto i:g[p]){
        int v=i.fi,e=i.se;
        if(!d[v]||vis[e]) continue;
        d[p]--,d[v]--,vis[e]=1;
        if(dfs(x)) return 1;
        d[p]++,d[v]++,vis[e]=0;
    }
    return 0;
}

int main() {
    int m;
    while(cin>>n>>m){
        for(int i=1;i<=n;++i)
            cin>>d[i],id[i]=i,g[i].clear();
        for(int i=1;i<=m;++i){
            int a,b;cin>>a>>b;
            g[a].push_back({b,i});
            g[b].push_back({a,i});
            vis[i]=0;
        }
        sort(id+1,id+n+1,cmp);
        if(dfs(1)) cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

1 or 2

原文：https://www.cnblogs.com/CADCADCAD/p/13299689.html