Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- vector<pair<int, int> > ans;
- int num = 0;
- vector<bool> used(20000, false);
- int timer, tin[20000], fup[20000];
- void dfs (int v, int p, vector<vector<int> >& g){
- used[v] = true;
- tin[v] = fup[v] = timer++;
- for (int i = 0; i < g[v].size(); ++i) {
- int to = g[v][i];
- if (to == p) continue;
- if (used[to])
- fup[v] = min (fup[v], tin[to]);
- else {
- dfs (to, v, g);
- fup[v] = min (fup[v], fup[to]);
- if (fup[to] > tin[v]){
- num++;
- ans.push_back({v, to});
- }
- }
- }
- }
- void find_bridges(int n, vector<vector<int> >& g){
- timer = 0;
- for (int i = 0; i < n; ++i)
- if (!used[i])
- dfs (i, -1, g);
- }
- bool compare(pair<int, int> a, pair<int, int> b){
- return(a.first == b.first && a.second == b.second || a.first == b.second && a.second == b.first);
- }
- int main() {
- int n, m, x, y;
- cin >> n >> m;
- vector<pair<int, int> > numbers(m);
- vector<vector<int> > g(n);
- vector<bool> used (n, false);
- for(int i = 0; i < m; i++){
- cin >> x >> y;
- g[x-1].push_back(y-1);
- g[y-1].push_back(x-1);
- numbers[i].first = x-1;
- numbers[i].second = y-1;
- }
- find_bridges(n, g);
- vector<int> ans1;
- for(int i = 0; i < ans.size(); i++) {
- int l = 0, nu = 0;
- for (int j = 0; j < m; j++)
- if (compare(ans[i], numbers[j])){
- l++;
- nu = j+1;
- }
- if(l == 1)
- ans1.push_back(nu);
- else
- num--;
- }
- cout << num << endl;
- sort(ans1.begin(), ans1.end());
- for(auto x : ans1)
- cout << x << " ";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement