Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <string>
- #include <cstdio>
- #include <set>
- #include <map>
- #include <sstream>
- #include <iterator>
- #include <cmath>
- #include <unordered_map>
- #include <queue>
- using namespace std;
- void dfs(int u, int p, int dep, vector< vector<int> > &g,
- vector<int> &d, vector<int> &fup, set<pair<int, int>> &bridges){
- d[u] = fup[u] = dep;
- for (int i = 0; i < g[u].size(); ++i){
- if(g[u][i] == p)
- continue;
- if(d[g[u][i]] != -1)
- fup[u] = min(fup[u], d[g[u][i]]);
- else{
- dfs(g[u][i], u, dep + 1, g, d, fup, bridges);
- fup[u] = min(fup[u], fup[g[u][i]]);
- if(fup[g[u][i]] > d[u])
- bridges.insert(make_pair(u, g[u][i]));
- }
- }
- }
- int main(){
- ios_base::sync_with_stdio(false);
- int n, m;
- cin >> n >> m;
- vector< vector<int> > g(n);
- map<pair<int, int>, int> edges;
- for (int i = 0; i < m; ++i){
- int x, y;
- cin >> x >> y;
- edges[make_pair(x - 1, y - 1)] = i;
- edges[make_pair(y - 1, x - 1)] = i;
- g[x - 1].push_back(y - 1);
- g[y - 1].push_back(x - 1);
- }
- vector<int> d(n, -1);
- vector<int> fup(n);
- set<pair<int, int>> bridges;
- for (int i = 0; i < n; ++i)
- if(d[i] == -1)
- dfs(i, i, 0, g, d, fup, bridges);
- vector<int> ans;
- for(auto it = bridges.begin(); it != bridges.end(); ++it)
- ans.push_back(edges[*it] + 1);
- sort(ans.begin(), ans.end());
- cout << ans.size() << endl;
- for (int i = 0; i < ans.size(); ++i)
- cout << ans[i] << " ";
- cout << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement