#include <iostream> #include <vector> #include <algorithm> using namespace std; vector<pair<int,int>> Es, Ed; vector<vector<int>> Gs, Gd; vector<bool> Used; struct ResultEntity { bool add; int x, y; }; vector<ResultEntity> Result; void dfs1(int v) { Used[v] = true; for (int nei : Gs[v]) if (!Used[nei]) { if (!binary_search(Es.begin(), Es.end(), pair<int,int>{0, nei})) Result.push_back({true, 0, nei}); dfs1(nei); } } void dfs2(int v) { Used[v] = false; for (int nei : Gd[v]) if (Used[nei]) { dfs2(nei); if (!binary_search(Ed.begin(), Ed.end(), pair<int,int>{0, nei})) Result.push_back({false, 0, nei}); } } void load_graph(int n, int& m, vector<pair<int,int>>& E, vector<vector<int>>& G) { cin >> m; E.resize(m); G.resize(n); for (int i=0; i<m; i++) { cin >> E[i].first >> E[i].second; E[i].first--; E[i].second--; if (E[i].first > E[i].second) swap(E[i].first, E[i].second); G[E[i].first].push_back(E[i].second); G[E[i].second].push_back(E[i].first); } sort(E.begin(), E.end()); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // input int n, ms, md; cin >> n; Used.resize(n, false); load_graph(n, ms, Es, Gs); load_graph(n, md, Ed, Gd); // phase 1 - make a star framework dfs1(0); // phase 2 - correct almost all edges for (int si=0,di=0; si<ms || di<md; ) { if (si<ms && (di==md || Es[si] < Ed[di])) { if (Es[si].first && Es[si].second) Result.push_back({false, Es[si].first, Es[si].second}); si++; } else if (di<md && (si==ms || Es[si] > Ed[di])) { if (Ed[di].first && Ed[di].second) Result.push_back({true, Ed[di].first, Ed[di].second}); di++; } else { si++; di++; } } // phase 3 - remove the framework dfs2(0); // output cout << Result.size() << '\n'; for (auto& result : Result) cout << (result.add ? '+' : '-') << ' ' << result.x+1 << ' ' << result.y+1 << '\n'; return 0; }
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 | #include <iostream> #include <vector> #include <algorithm> using namespace std; vector<pair<int,int>> Es, Ed; vector<vector<int>> Gs, Gd; vector<bool> Used; struct ResultEntity { bool add; int x, y; }; vector<ResultEntity> Result; void dfs1(int v) { Used[v] = true; for (int nei : Gs[v]) if (!Used[nei]) { if (!binary_search(Es.begin(), Es.end(), pair<int,int>{0, nei})) Result.push_back({true, 0, nei}); dfs1(nei); } } void dfs2(int v) { Used[v] = false; for (int nei : Gd[v]) if (Used[nei]) { dfs2(nei); if (!binary_search(Ed.begin(), Ed.end(), pair<int,int>{0, nei})) Result.push_back({false, 0, nei}); } } void load_graph(int n, int& m, vector<pair<int,int>>& E, vector<vector<int>>& G) { cin >> m; E.resize(m); G.resize(n); for (int i=0; i<m; i++) { cin >> E[i].first >> E[i].second; E[i].first--; E[i].second--; if (E[i].first > E[i].second) swap(E[i].first, E[i].second); G[E[i].first].push_back(E[i].second); G[E[i].second].push_back(E[i].first); } sort(E.begin(), E.end()); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // input int n, ms, md; cin >> n; Used.resize(n, false); load_graph(n, ms, Es, Gs); load_graph(n, md, Ed, Gd); // phase 1 - make a star framework dfs1(0); // phase 2 - correct almost all edges for (int si=0,di=0; si<ms || di<md; ) { if (si<ms && (di==md || Es[si] < Ed[di])) { if (Es[si].first && Es[si].second) Result.push_back({false, Es[si].first, Es[si].second}); si++; } else if (di<md && (si==ms || Es[si] > Ed[di])) { if (Ed[di].first && Ed[di].second) Result.push_back({true, Ed[di].first, Ed[di].second}); di++; } else { si++; di++; } } // phase 3 - remove the framework dfs2(0); // output cout << Result.size() << '\n'; for (auto& result : Result) cout << (result.add ? '+' : '-') << ' ' << result.x+1 << ' ' << result.y+1 << '\n'; return 0; } |