ZOJ 3732 可图性判定--Havel-Hakimi定理

淩亂°似流年 2022-05-03 00:28 177阅读 0赞

题意：给定n个点度数，问是否可以构造一个简单图。

思路：Havel-Hakimi定理 ：

1.将度数从小到大排序

2.用第一个向后面连续d\[1\]个点连边,若点数不够则不能构造

3.若点数够，则将每个点度数减1，若出现负值，则不能构造，

4.去掉该点返回步骤一，直到集合中没有点。

对于多个图，只需要判定i+d\[i\]和i+d\[i\]+1这两个点度数是否一致，

若一致就交换。即可达到不同图的目标。

#include<bits/stdc++.h>
    #define fir first
    #define sec second
    using namespace std;
    const int N=110;
    int deg[N];
    int n;
    vector<int> u[2], v[2];
    
    bool havel(){
        int tmp[N];
        for(int i=1; i<=n; i++)
            tmp[i]=deg[i];
        for(int i=1; i<n; i++){
            sort(tmp+i, tmp+1+n, greater<int>());
            if(tmp[i] > n-i) return false;
            for(int j=1; j<=tmp[i]; j++){
                tmp[i+j]--;
                if(tmp[i+j]<0) return false;
            }
        }
        return true;
    }
    
    bool cmp(pair<int, int> a, pair<int, int> b){
        return a.fir>b.fir;
    }
    
    bool solve(){
        pair<int,int> p[N];
        for(int i=1; i<=n; i++)
            p[i].fir=deg[i], p[i].sec=i;
        bool ok=false;
        for(int i=1; i<=n; i++){
            sort(p+i, p+1+n, cmp);
    
            if(i+p[i].fir<n && p[i+p[i].fir].fir==p[i+p[i].fir+1].fir && p[i+p[i].fir].fir!=0){
                ok=true;
            }
            for(int j=1; j<=p[i].fir; j++){
                u[0].push_back(p[i].sec);
                v[0].push_back(p[i+j].sec);
                p[i+j].fir--;
            }
    
        }
    
        if(!ok) return true;
    
        for(int i=1; i<=n; i++)
            p[i].fir=deg[i], p[i].sec=i;
    
        for(int i=1; i<=n; i++){
            sort(p+i, p+1+n, cmp);
    
            if(i+p[i].fir<n && p[i+p[i].fir].fir==p[i+p[i].fir+1].fir && p[i+p[i].fir].fir!=0){
                swap(p[i+p[i].fir].sec, p[i+p[i].fir+1].sec);
            }
    
            for(int j=1; j<=p[i].fir; j++){
                u[1].push_back(p[i].sec);
                v[1].push_back(p[i+j].sec);
                p[i+j].fir--;
            }
    
        }
    
        return false;
    }
    
    int main(){
        while(~scanf("%d", &n)){
            u[0].clear(); u[1].clear();
            v[0].clear(); v[1].clear();
            for(int i=1; i<=n; i++)
                scanf("%d", deg+i);
    
            if(!havel()){
                printf("IMPOSSIBLE\n");
            }
            else{
    
                    if(solve()){
                        printf("UNIQUE\n");
                        printf("%d %d\n", n, u[0].size());
                        if(u[0].size()) printf("%d", u[0][0]);
                        for(int i=1; i<u[0].size(); i++)
                            printf(" %d", u[0][i]);
                        puts("");
                        if(v[0].size()) printf("%d", v[0][0]);
                        for(int i=1; i<v[0].size(); i++)
                            printf(" %d", v[0][i]);
                        puts("");
                    }
                    else{
                        printf("MULTIPLE\n");
                        printf("%d %d\n", n, u[0].size());
                        if(u[0].size()) printf("%d", u[0][0]);
                        for(int i=1; i<u[0].size(); i++)
                            printf(" %d", u[0][i]);
                        puts("");
                        if(v[0].size()) printf("%d", v[0][0]);
                        for(int i=1; i<v[0].size(); i++)
                            printf(" %d", v[0][i]);
                        puts("");
    
                        printf("%d %d\n", n, u[1].size());
                        if(u[1].size()) printf("%d", u[1][0]);
                        for(int i=1; i<u[1].size(); i++)
                            printf(" %d", u[1][i]);
                        puts("");
                        if(v[1].size()) printf("%d", v[1][0]);
                        for(int i=1; i<v[1].size(); i++)
                            printf(" %d", v[1][i]);
                        puts("");
                        }
    
                }
    
        }
    
        return 0;
    }