Znzryb's Blog
0%

Refact.ai Match 1 (Codeforces Round 985)—D. Cool Graph

Posted on Edited on

思路讲解

主要思路与洛谷题解类似

主要思路就是先把所有点给打散，再连起来

打散比较简单，发现这个点入度≥2就持续删边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(int i=1;i<=n;++i) {
            if(g[i].size()>=2) {    // 入度>=2
                vector<int> temp;
                for(set<int> :: iterator it=g[i].begin();it!=g[i].end();++it) {
                    temp.push_back(*it);
                }
                while (temp.size()>1) {
                    int a=temp.back();
                    temp.pop_back();
                    int b=temp.back();
                    del(i,a,b);
                }
            }
        }

重新连起来需要root1和root2，否则连不起来

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// root,root2就是根，所有的操作都是他衍生出来的
if(!isCool) {
    for(int i=1;i<=n;++i) {
        if(vis[i])
            continue;
        vis[i]=true;
        add(root,root2,i);
        root2=i;
        if(g[i].size()==0) {
            continue;
        }
        vis[*g[i].begin()]=true;
    }
}

AC代码

https://codeforces.com/contest/2029/submission/292760535

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N=static_cast<int>(1e5)+10;
int n,T,m;
set<int> g[N];
bitset<N> vis;
struct op {
    int a,b,c;
};
vector<op> ans;

inline void del(int a,int b, int c) {
    op temp;
    temp.a=a,temp.b=b,temp.c=c;
    ans.push_back(temp);
    // 删除
    g[a].erase(b);g[a].erase(c);
    g[b].erase(a);g[c].erase(a);
    // a与b，c关系明晰，但是b，c关系不明，故需要检验判断
    if(g[b].count(c)==1)
        g[b].erase(c),g[c].erase(b);
    else
        g[b].insert(c),g[c].insert(b);
}

inline void add(int a,int b,int c) {
    op temp;
    temp.a=a,temp.b=b,temp.c=c;
    ans.push_back(temp);
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cin>>T;
    while (T--) {
        cin>>n>>m;
        vis.reset();    // 初始化
        for(int i=1;i<=n;++i) {
            g[i].clear();
        }
        ans.clear();
        if(m==0) {
            cout<<0<<endl;
            continue;
        }
        for(int _=1;_<=m;++_) {
            int a,b;
            cin>>a>>b;
            g[a].insert(b);     // g里面其实是个set
            g[b].insert(a);
        }
        for(int i=1;i<=n;++i) {
            if(g[i].size()>=2) {    // 入度>=2
                vector<int> temp;
                for(set<int> :: iterator it=g[i].begin();it!=g[i].end();++it) {
                    temp.push_back(*it);
                }
                while (temp.size()>1) {
                    int a=temp.back();
                    temp.pop_back();
                    int b=temp.back();
                    temp.pop_back();
                    del(i,a,b);
                }
            }
        }
        bool isCool=true;
        int root,root2;
        for(int i=1;i<=n;++i) {     // 检验是否删完以后成为空图了
            if(g[i].size()==1) {
                isCool=false;
                root=i;
                root2=*g[i].begin();
                vis[i]=true,vis[*g[i].begin()]=true;
                break;
            }
        }
        // root,root2就是根，所有的操作都是他衍生出来的
        if(!isCool) {
            for(int i=1;i<=n;++i) {
                if(vis[i])
                    continue;
                vis[i]=true;
                add(root,root2,i);
                root2=i;
                if(g[i].size()==0) {
                    continue;
                }
                vis[*g[i].begin()]=true;
            }
        }
        cout<<ans.size()<<"\n";
        for(int i=0;i<ans.size();++i) {
            cout<<ans[i].a<<" "<<ans[i].b<<" "<<ans[i].c<<"\n";
        }
    }
    return 0;
}
// AC https://codeforces.com/contest/2029/submission/292760535

心路历程（WA，TLE，MLE……）

原来的思路是找环，删点，但发现无向图找环很麻烦，也无法满足我的需求，于是还是决定变树。

无向图找环，用dfs加dsu（并查集）

如果不太会的话建议左转去做leetcode684冗余连接

初始化要彻底

1
2
3
4
5
vis.reset();    // 初始化
for(int i=1;i<=n;++i) {
    g[i].clear();
}
ans.clear();