Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <set>
- using namespace std;
- const int INF = (int)1e9;
- const int NEUTRALMIN = INF;
- const int NEUTRALMAX = -INF;
- const int MAXN = (int)1e5;
- const int P = 239017;
- const int MOD = 1000000007;
- vector < vector <int> > gg;
- bool used[MAXN];
- int tin[MAXN];
- int low_time[MAXN];
- int cur_time;
- vector <int> points;
- void dfs(int v, int par) {
- int childs = 0;
- used[v] = true;
- tin[v] = cur_time;
- low_time[v] = cur_time++;
- bool point = false;
- for (int i = 0; i < (int)gg[v].size(); i++) {
- int to = gg[v][i];
- if (to == par)
- continue;
- if (!used[to]) {
- dfs(to, v);
- childs++;
- if (tin[v] <= low_time[to])
- point = true;
- else {
- low_time[v] = min(low_time[v], low_time[to]);
- }
- } else {
- // Found backedge
- low_time[v] = min(low_time[v], tin[to]);
- }
- }
- if ((par == -1 && childs > 1) || (par != -1 && point)) {
- points.push_back(v);
- }
- }
- void outputMe() {
- sort(points.begin(), points.end());
- points.resize(unique(points.begin(), points.end()) - points.begin());
- cout << points.size() << endl;
- for (int i = 0; i < (int)points.size(); i++) {
- cout << points[i] + 1 << " ";
- }
- }
- int main() {
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- int n, m, st;
- cin >> n >> m;
- gg.resize(n);
- for (int i = 0; i < m; i++) {
- int a, b;
- cin >> a >> b;
- --a, --b;
- gg[a].push_back(b);
- gg[b].push_back(a);
- st = a;
- }
- for (int i = 0; i < n; i++) {
- if (!used[i])
- dfs(i, -1);
- }
- outputMe();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement