首页 > 代码库 > 9E-并查集
9E-并查集
给你n个点,这n个点之间有m条边相连,问能不能再添加几条边,使这n个点刚好能围成一个圈
#include <iostream>#include <vector>#define pii pair <int, int>#define mp make_pairusing namespace std;vector <vector <int> > G;vector <bool> mark;vector <pii> res;bool cycle = 0;void dfs(int u, int p = -1){ mark[u] = 1; int i; for (i = 0; i < G[u].size(); i++) { if (!mark[G[u][i]]) dfs(G[u][i], u); else if (G[u][i] != p) cycle = 1; }}bool check_res(){ int i; for (i = 0; i < G.size(); i++) if (G[i].size() != 2 || !mark[i]) return 0; return 1;}bool check_good(){ int i; for (i = 0; i < G.size(); i++) if (G[i].size() > 2) return 0; return 1;}void add(){ int i, j; for (i = 0; i < G.size(); i++) for (j = i + 1; j < G.size(); j++) if (G[i].size() < 2 && G[j].size() < 2) { mark.assign(G.size(), 0); dfs(i); if (!mark[j]) { res.push_back(mp(i, j)); G[i].push_back(j); G[j].push_back(i); } }}int main(){ int n, m, i, a, b; cin >> n >> m; G.resize(n); mark.resize(n); if (n == 1) { if (m == 0) cout << "YES\n1\n1 1\n"; else if (m == 1) cout << "YES\n0\n"; else cout << "NO\n"; return 0; } for (i = 0; i < m; i++) { cin >> a >> b; if (a == b) { cout << "NO" << endl; return 0; } G[a - 1].push_back(b - 1); G[b - 1].push_back(a - 1); } dfs(0); if (check_res()) { cout << "YES" << endl; cout << 0 << endl; } else if (check_good() && m <= n && !cycle) { cout << "YES" << endl; add(); cout << res.size() + 1 << endl; a = -1, b = -1; for (i = 0; i < res.size(); i++) cout << res[i].first + 1 << " " << res[i].second + 1 << endl; for (i = 0; i < G.size(); i++) if (G[i].size() < 2) { if (a == -1) a = i; else b = i; } cout << a + 1 << " " << b + 1 << endl; } else cout << "NO" << endl; return 0;}
9E-并查集
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。