2024杭电多校第6场 1002.造花(困难版)

1002

提供一种不同于正解的做法

重新定义菊花图：

菊花图首先是一棵树，其次存在一个点，它指向的点的度数都为1，剩下的都是度数为1的点。

那么在枚举删去某个点u时，只需要：

1.给u的邻点的度数-1（deg[u]--)

2.维护当前度数不为1的点的个数（代码里的non1）

3.维护 指向的点都为1度点的 点的个数（代码里的all1），实现时多开了一个cnt1[ ]表示某个点指向的1度点的个数，如果cnt1[u]==deg[u]且deg[u]>1，则该点是菊花图中心。

4.判定当前剩下的图是否为菊花图需要：all1==non1(说明度数不为1的点都是菊花图中心，则整个图一定是若干个菊花图）

实现时还有一些细节：

1.如果原图本来就是菊花图，把所有点都输出

2.如果原图有两个及两个以上的连通块不是菊花图，则无解

3.原图只有一个连通块不是菊花图，其他都是，这种情况有解，但要注意在枚举删去的点时，要把其他连通块里的点ban掉。

#include<bits/stdc++.h>
using namespace std;
const int N =2e5+5;
int n,m,cnt=0,tot=0,mx=0,deg[N],vis[N],cnt1[N];
vector<int>e[N];
void dfs(int u,int p){
    cnt++;
    vis[u]=1;
    tot+=e[u].size();
    mx=max(mx,(int)e[u].size());
    for(auto v:e[u]){
        if(vis[v]) continue;
        dfs(v,u);
    }
}
int example;
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        deg[i]=0;
        cnt1[i]=0;
        vis[i]=0;
        e[i].clear();
    }
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
        deg[u]++,deg[v]++;
    }
    int G=0,pos=-1;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            cnt=0,tot=0,mx=0;
            dfs(i,0);
            if( cnt-1==tot/2 && mx==cnt-1) {}// 判断是否是菊花图
            else {
                G++;pos=i;
            }
        }
    }
    
    if(G>=2){
        cout<<-1<<"\n";
        return;
    }
    else if(G==1){
        for(int i=1;i<=n;i++) vis[i]=0;
        dfs(pos,0);
        
        set<int>s;
        int non1=0,all1=0;
        for(int i=1;i<=n;i++){
            if(!vis[i]) continue;
            if(deg[i]>1) non1++;
            for(auto v:e[i]){
                if(e[v].size()==1) cnt1[i]++;
            }
            if(cnt1[i]==(int)e[i].size()) all1++;
        }
        for(int i=1;i<=n;i++){
            if(!vis[i]) continue;
            for(auto v:e[i]){
                deg[v]--;
            }
            int add_all1=0;
            int add_non1=0;
            if(e[i].size()>1) add_non1=-1;
            set<int>newG;
            for(auto v:e[i]){
                if(deg[v]==1){
                    for(auto to:e[v]){
                        if(to==i) continue;
                        cnt1[to]++;
                        if(cnt1[to]==deg[to]&&deg[to]>1) newG.insert(to);
                    }
                    add_non1--;
                }
                else {
                    if(cnt1[v]==deg[v]&&deg[v]>1) newG.insert(v);
                }
            }
            add_all1=newG.size();
            if(all1+add_all1==non1+add_non1) s.insert(i);
            for(auto v:e[i]) {
                deg[v]++;
                if(deg[v]==2){
                    for(auto to:e[v]){
                        if(to==i) continue;
                        cnt1[to]--;
                    }
                }
            }
        }
        if(s.size()==0) cout<<-1<<"\n";
        else {
            for(auto v:s) {
                if(v!=(*s.rbegin()))cout<<v<<" ";
                else cout<<v;
            }
            cout<<"\n";
        }
    }
    else {
        for(int i=1;i<=n;i++) {
            if(i!=n) cout<<i<<" ";
            else cout<<i;
        }
        cout<<"\n";
    }
}
int main(){
//    freopen("1002.in","r",stdin);
//    freopen("lys.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--){
        example++;
        solve();
    }
}
/*
9 6
5 4
6 4
4 9
8 7
7 9
7 2
*/