#include <bits/stdc++.h> using namespace std; struct st{ char c; int a, b; }; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; int ms; cin >> ms; vector <vector<int>> graphs(n+1); map <pair<int, int>, bool> edges; while(ms--){ int a, b; cin >> a >> b; graphs[a].push_back(b); graphs[b].push_back(a); edges[{min(a, b), max(a, b)}] = true; } int md; cin >> md; vector <vector<int>> graphd(n+1); map <pair<int, int>, bool> edged; while(md--){ int a, b; cin >> a >> b; graphd[a].push_back(b); graphd[b].push_back(a); edged[{min(a, b), max(a, b)}] = true; } vector <st> res; vector <bool> viss(n+1); queue <int> q; viss[1] = true; q.push(1); while(!q.empty()){ int act = q.front(); q.pop(); if(act != 1 && !edges[{1, act}]) res.push_back({'+', 1, act}); for(auto ne: graphs[act]){ if(!viss[ne]){ q.push(ne); viss[ne] = true; } } } for(auto e: edged){ int u = e.first.first, v = e.first.second; if(u != 1 && v != 1 && !edges[{u, v}]) res.push_back({'+', u, v}); } for(auto e: edges){ int u = e.first.first, v = e.first.second; if(u != 1 && v != 1 && !edged[{u, v}]) res.push_back({'-', u, v}); } vector <bool> visd(n+1); q.push(1); visd[1] = true; stack <int> order; while(!q.empty()){ int act = q.front(); if(act != 1) order.push(act); q.pop(); for(auto ne: graphd[act]){ if(!visd[ne]){ q.push(ne); visd[ne] = true; } } } while(!order.empty()){ int act = order.top(); order.pop(); if(!edged[{1, act}]) res.push_back({'-', 1, act}); } cout << res.size() << "\n"; for(auto r: res) cout << r.c << " " << r.a << " " << r.b << "\n"; }
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 104 105 106 107 | #include <bits/stdc++.h> using namespace std; struct st{ char c; int a, b; }; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; int ms; cin >> ms; vector <vector<int>> graphs(n+1); map <pair<int, int>, bool> edges; while(ms--){ int a, b; cin >> a >> b; graphs[a].push_back(b); graphs[b].push_back(a); edges[{min(a, b), max(a, b)}] = true; } int md; cin >> md; vector <vector<int>> graphd(n+1); map <pair<int, int>, bool> edged; while(md--){ int a, b; cin >> a >> b; graphd[a].push_back(b); graphd[b].push_back(a); edged[{min(a, b), max(a, b)}] = true; } vector <st> res; vector <bool> viss(n+1); queue <int> q; viss[1] = true; q.push(1); while(!q.empty()){ int act = q.front(); q.pop(); if(act != 1 && !edges[{1, act}]) res.push_back({'+', 1, act}); for(auto ne: graphs[act]){ if(!viss[ne]){ q.push(ne); viss[ne] = true; } } } for(auto e: edged){ int u = e.first.first, v = e.first.second; if(u != 1 && v != 1 && !edges[{u, v}]) res.push_back({'+', u, v}); } for(auto e: edges){ int u = e.first.first, v = e.first.second; if(u != 1 && v != 1 && !edged[{u, v}]) res.push_back({'-', u, v}); } vector <bool> visd(n+1); q.push(1); visd[1] = true; stack <int> order; while(!q.empty()){ int act = q.front(); if(act != 1) order.push(act); q.pop(); for(auto ne: graphd[act]){ if(!visd[ne]){ q.push(ne); visd[ne] = true; } } } while(!order.empty()){ int act = order.top(); order.pop(); if(!edged[{1, act}]) res.push_back({'-', 1, act}); } cout << res.size() << "\n"; for(auto r: res) cout << r.c << " " << r.a << " " << r.b << "\n"; } |