本题需要将一张图分为两个顶点覆盖(vertex cover),并不需要最小,较简单。
dfs染色,任一点起,每个相连点染成不同颜色,若出现染过色,且该点颜色与当前应该染成的颜色不同,则出错。
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
| #include<iostream> #include<vector> #include<map> using namespace std; const int maxn = 1e5 + 5; int vised[maxn]; map<int, vector<int> >mp; struct Node { vector<int>to; }nd[maxn]; bool flg = 1; void paint(int s,int color) { if (vised[s] != 0) { if (vised[s] != color) flg = 0; return; } vised[s] = color; mp[color].push_back(s); for (auto c : nd[s].to) { paint(c, 0 - color); } } int main() { mp[-1] = {}; mp[1] = {}; int n, m; cin >> n >> m; for (int i = 0; i < m; i++) { int u, v; cin >> u>> v; nd[u].to.push_back(v); nd[v].to.push_back(u); } for (int i = 1; i <= n; i++) { if (!vised[i]) paint(i,1); if (flg == false) { cout << -1; return 0; } } cout << mp[-1].size()<<endl; for (auto c : mp[-1]) cout << c << ' '; cout << endl; cout << mp[1].size() << endl; for (auto c : mp[1]) cout << c << ' '; return 0; }
|