Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #pragma GCC optimize("Ofast")
- void dfs(int v, vector<int> &marc, const vector<vector<pair<int, int>>> &grafo, int &qnt, int x)
- {
- marc[v] = 1; --qnt;
- for (auto [viz, e] : grafo[v]) if (!marc[viz] && e != x) dfs(viz, marc, grafo, qnt, x);
- }
- void getMatters(int v, vector<int> &marc, const vector<vector<pair<int, int>>> &grafo, vector<int> &matters)
- {
- marc[v] = 1;
- for (auto [viz, e] : grafo[v]) if (!marc[viz]) {matters[e] = 1; getMatters(viz, marc, grafo, matters);}
- }
- int main()
- {
- ios_base::sync_with_stdio(false); cin.tie(NULL);
- int N, M; cin >> N >> M;
- array<vector<vector<pair<int, int>>>, 2> grafo; grafo[0].resize(N+1); grafo[1].resize(N+1);
- vector<pair<int, int>> edges(M);
- for (int i = 0; i < M; i++) {auto &[x, y] = edges[i]; cin >> x >> y; grafo[0][x].emplace_back(y, i); grafo[1][y].emplace_back(x, i);}
- vector<int> matters(M), marc(N+1);
- getMatters(1, marc, grafo[0], matters);
- fill(marc.begin(), marc.end(), 0);
- getMatters(1, marc, grafo[1], matters);
- vector<pair<int, int>> resp; resp.reserve(M);
- for (int i = 0; i < M; i++)
- {
- if (!matters[i]) continue;
- auto [x, y] = edges[i];
- vector<int> marc0(N+1, 0), marc1(N+1, 0); int qnt0 = N, qnt1 = N;
- dfs(1, marc0, grafo[0], qnt0, i); dfs(1, marc1, grafo[1], qnt1, i);
- if (qnt0 || qnt1) resp.emplace_back(x, y);
- }
- cout << resp.size() << '\n';
- for (auto [x, y] : resp) cout << x << " " << y << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
