Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <fstream>
- using namespace std;
- vector < vector <int> > g, num;
- vector <int> used, tin, tup;
- set <int> ans, ans2;
- int timer = 0;
- void dfs(int v, int predok, int nomer){
- timer++;
- used[v] = 1;
- tin[v] = timer;
- tup[v] = timer;
- for (int i = 0; i < g[v].size(); i++){
- int to = g[v][i];
- if (used[to] == 0){
- dfs(to, v, num[v][i]);
- tup[v] = min(tup[v], tup[to]);
- }
- else if (nomer != num[v][i]){
- tup[v] = min(tup[v], tin[to]);
- }
- // if (check.count({predok, i}) > 1 || check.count({i, predok}) > 1){
- // nr = -15;
- // }
- }
- if (tup[v] > tin[predok] && predok != -1){
- ans.insert(nomer);
- }
- }
- void dfs2(int v){
- used[v] = 1;
- for (int i = 0; i < g[v].size(); i++){
- int to = g[v][i];
- if (used[to] == 0){
- if (ans.count(num[v][i]) && num[v][i] != - 1){
- //cout << num[v][i] << endl;
- ans2.insert(num[v][i]);
- }
- dfs2(to);
- }
- }
- }
- int main(){
- // freopen("bridges.in", "r", stdin);
- // freopen("bridges.out", "w", stdout);
- int n, m, x, y;
- cin >> n >> m;
- g.resize(n);
- used.resize(n, 0);
- tin.resize(n);
- tup.resize(n);
- num.resize(n);
- for (int i = 0; i < m; i++){
- cin >> x >> y;
- x--;
- y--;
- g[x].push_back(y);
- g[y].push_back(x);
- num[x].push_back(i + 1);
- num[y].push_back(i + 1);
- // check.insert({x, y});
- // check.insert({y, x});
- }
- //cout<<"input correct"<<endl;
- dfs(0, -1, -1);
- used.assign(n, 0);
- dfs2(0);
- cout << ans2.size() << endl;
- for (set<int>::iterator it = ans2.begin(); it != ans2.end(); ++it) {
- cout << *it << " ";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement