#include <cstdio> #include <vector> #include <utility> #include <set> #include <queue> using namespace std; int n, ms, md; vector<int> G[30100]; vector<pair<int, int> > u_log; vector<pair<int, int> > b_log; vector<vector<pair<int, int> > > uu_log; vector<vector<pair<int, int> > > ub_log; vector<pair<int, int> > ub_p; vector<pair<int, int> > uu_p; int all_cmds; set<pair<int, int> > dod; set<pair<int, int> > e; // do usuniecia? bool byl[30100]; int ojciec[30100]; vector<int> BFS(int s, int d, bool rem = false) { queue<int> Q; Q.push(s); int v = s; for(int i = 1; i <= n; i++) { byl[i] = 0; ojciec[i] = 0; } while(v != d) { for(int i = 0; i < G[v].size(); i++) { if(rem && v == s && G[v][i] == d) continue; if(!byl[G[v][i]]) { Q.push(G[v][i]); byl[G[v][i]] = 1; ojciec[G[v][i]] = v; } } v = Q.front(); Q.pop(); } vector<int> path; while(v != s) { path.push_back(v); v = ojciec[v]; } path.push_back(s); return path; } int main() { scanf("%d", &n); scanf("%d", &ms); for(int i = 0; i < ms; i++) { int a, b; scanf("%d %d", &a, &b); G[a].push_back(b); G[b].push_back(a); if(a < b) e.insert(make_pair(a, b)); else e.insert(make_pair(b, a)); } scanf("%d", &md); vector<pair<int, int> > tmp; for(int i = 0; i < md; i++) { int a, b; scanf("%d %d", &a, &b); if(a > b) swap(a, b); pair<int, int> p(a, b); if(e.contains(p)) tmp.push_back(p); else dod.insert(p); } for(int i = 0; i < tmp.size(); i++) e.erase(tmp[i]); while(!dod.empty()) { set<pair<int, int> >::iterator it = dod.begin(); vector<int> path = BFS(it->first, it->second); for(int j = path.size() - 3; j >= 0; j--) { int a = path[path.size() - 1]; int b = path[j]; if(a > b) swap(a, b); b_log.push_back(make_pair(a, b)); G[a].push_back(b); G[b].push_back(a); pair<int, int> p(a, b); if(dod.contains(p)) dod.erase(p); else u_log.push_back(p); } } for(int i = u_log.size() - 1; i >= 0; i--) { int a = u_log[i].first; int b = u_log[i].second; for(int j = 0; j < G[a].size(); j++) if(G[a][j] == b) { G[a].erase(G[a].begin() + j); break; } for(int j = 0; j < G[b].size(); j++) { if(G[b][j] == a) G[b].erase(G[b].begin() + j); break; } } for(set<pair<int, int> >::iterator i = e.begin(); i != e.end(); i++) { vector<int> path = BFS(i->first, i->second, true); ub_p.clear(); uu_p.clear(); for(int j = path.size() - 3; j > 0; j--) { int a = path[path.size() - 1]; int b = path[j]; if(a > b) swap(a, b); ub_p.push_back(make_pair(a, b)); pair<int, int> p(a, b); uu_p.push_back(p); } int a = i->first; int b = i->second; if(a > b) swap(a, b); uu_p.push_back(make_pair(a, b)); for(int j = 0; j < G[a].size(); j++) if(G[a][j] == b) { G[a].erase(G[a].begin() + j); break; } for(int j = 0; j < G[b].size(); j++) { if(G[b][j] == a) G[b].erase(G[b].begin() + j); break; } uu_log.push_back(uu_p); all_cmds += uu_p.size(); ub_log.push_back(ub_p); all_cmds += ub_p.size(); } all_cmds += b_log.size(); all_cmds += u_log.size(); printf("%d\n", all_cmds); for(int i = 0; i < b_log.size(); i++) printf("+ %d %d\n", b_log[i].first, b_log[i].second); for(int i = u_log.size() - 1; i >= 0; i--) printf("- %d %d\n", u_log[i].first, u_log[i].second); for(int i = 0; i < ub_log.size(); i++) { for(int j = 0; j < ub_log[i].size(); j++) { printf("+ %d %d\n", ub_log[i][j].first, ub_log[i][j].second); } for(int j = uu_log[i].size() - 1; j >= 0; j--) { printf("- %d %d\n", uu_log[i][j].first, uu_log[i][j].second); } } 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 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 | #include <cstdio> #include <vector> #include <utility> #include <set> #include <queue> using namespace std; int n, ms, md; vector<int> G[30100]; vector<pair<int, int> > u_log; vector<pair<int, int> > b_log; vector<vector<pair<int, int> > > uu_log; vector<vector<pair<int, int> > > ub_log; vector<pair<int, int> > ub_p; vector<pair<int, int> > uu_p; int all_cmds; set<pair<int, int> > dod; set<pair<int, int> > e; // do usuniecia? bool byl[30100]; int ojciec[30100]; vector<int> BFS(int s, int d, bool rem = false) { queue<int> Q; Q.push(s); int v = s; for(int i = 1; i <= n; i++) { byl[i] = 0; ojciec[i] = 0; } while(v != d) { for(int i = 0; i < G[v].size(); i++) { if(rem && v == s && G[v][i] == d) continue; if(!byl[G[v][i]]) { Q.push(G[v][i]); byl[G[v][i]] = 1; ojciec[G[v][i]] = v; } } v = Q.front(); Q.pop(); } vector<int> path; while(v != s) { path.push_back(v); v = ojciec[v]; } path.push_back(s); return path; } int main() { scanf("%d", &n); scanf("%d", &ms); for(int i = 0; i < ms; i++) { int a, b; scanf("%d %d", &a, &b); G[a].push_back(b); G[b].push_back(a); if(a < b) e.insert(make_pair(a, b)); else e.insert(make_pair(b, a)); } scanf("%d", &md); vector<pair<int, int> > tmp; for(int i = 0; i < md; i++) { int a, b; scanf("%d %d", &a, &b); if(a > b) swap(a, b); pair<int, int> p(a, b); if(e.contains(p)) tmp.push_back(p); else dod.insert(p); } for(int i = 0; i < tmp.size(); i++) e.erase(tmp[i]); while(!dod.empty()) { set<pair<int, int> >::iterator it = dod.begin(); vector<int> path = BFS(it->first, it->second); for(int j = path.size() - 3; j >= 0; j--) { int a = path[path.size() - 1]; int b = path[j]; if(a > b) swap(a, b); b_log.push_back(make_pair(a, b)); G[a].push_back(b); G[b].push_back(a); pair<int, int> p(a, b); if(dod.contains(p)) dod.erase(p); else u_log.push_back(p); } } for(int i = u_log.size() - 1; i >= 0; i--) { int a = u_log[i].first; int b = u_log[i].second; for(int j = 0; j < G[a].size(); j++) if(G[a][j] == b) { G[a].erase(G[a].begin() + j); break; } for(int j = 0; j < G[b].size(); j++) { if(G[b][j] == a) G[b].erase(G[b].begin() + j); break; } } for(set<pair<int, int> >::iterator i = e.begin(); i != e.end(); i++) { vector<int> path = BFS(i->first, i->second, true); ub_p.clear(); uu_p.clear(); for(int j = path.size() - 3; j > 0; j--) { int a = path[path.size() - 1]; int b = path[j]; if(a > b) swap(a, b); ub_p.push_back(make_pair(a, b)); pair<int, int> p(a, b); uu_p.push_back(p); } int a = i->first; int b = i->second; if(a > b) swap(a, b); uu_p.push_back(make_pair(a, b)); for(int j = 0; j < G[a].size(); j++) if(G[a][j] == b) { G[a].erase(G[a].begin() + j); break; } for(int j = 0; j < G[b].size(); j++) { if(G[b][j] == a) G[b].erase(G[b].begin() + j); break; } uu_log.push_back(uu_p); all_cmds += uu_p.size(); ub_log.push_back(ub_p); all_cmds += ub_p.size(); } all_cmds += b_log.size(); all_cmds += u_log.size(); printf("%d\n", all_cmds); for(int i = 0; i < b_log.size(); i++) printf("+ %d %d\n", b_log[i].first, b_log[i].second); for(int i = u_log.size() - 1; i >= 0; i--) printf("- %d %d\n", u_log[i].first, u_log[i].second); for(int i = 0; i < ub_log.size(); i++) { for(int j = 0; j < ub_log[i].size(); j++) { printf("+ %d %d\n", ub_log[i][j].first, ub_log[i][j].second); } for(int j = uu_log[i].size() - 1; j >= 0; j--) { printf("- %d %d\n", uu_log[i][j].first, uu_log[i][j].second); } } return 0; } |