Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <cstdio>
- #include <cstdlib>
- #include <vector>
- using namespace std;
- const int N = (int)1e5 + 10;
- struct Edge
- {
- int to, ind;
- Edge () {}
- Edge (int to, int ind) : to(to), ind(ind) {}
- };
- vector <Edge> g[N];
- vector <int> ans;
- int tin[N];
- int d[N];
- bool used[N];
- int tme = 0;
- void dfs(int v, int par = -1)
- {
- used[v] = 1;
- tin[v] = tme++;
- d[v] = tin[v];
- bool isPar = false;
- int cntChild = 0;
- int minVal = (int)1e9;
- for (int i = 0; i < (int)g[v].size(); i++)
- {
- int to = g[v][i].to;
- if (!used[to])
- {
- cntChild++;
- dfs(to, v);
- d[v] = min(d[v], d[to]);
- minVal = min(minVal, d[to]);
- }
- else
- {
- if ((to == par && isPar) || to != par)
- {
- d[v] = min(d[v], tin[to]);
- }
- if (to == par)
- isPar = true;
- }
- }
- if (par == -1 && cntChild > 1)
- ans.push_back(v);
- else if (par != -1 && minVal >= tin[v])
- ans.push_back(v);
- }
- int main()
- {
- int n, m;
- scanf("%d%d", &n, &m);
- for (int i = 0; i < m; i++)
- {
- int a, b;
- scanf("%d%d", &a, &b);
- g[a].push_back(Edge(b, i + 1));
- g[b].push_back(Edge(a, i + 1));
- }
- for (int i = 1; i <= n; i++)
- {
- if (!used[i])
- dfs(i);
- }
- sort(ans.begin(), ans.end());
- printf("%d\n", (int)ans.size());
- for (int i = 0; i < (int)ans.size(); i++)
- printf("%d ", ans[i]);
- return 0;
- }
- /*
- 9 12
- 1 2 1 3
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement