Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define all(a) (a).begin(), (a).end()
- #define ull unsigned long long
- #define ll long long
- #define ld long double
- #define PI 3.14159265358979323846
- using namespace std;
- int n, m;
- vector<vector<int>> v;
- vector<int> used, tin, up;
- set<int> res;
- int t = 0;
- void dfs(int u, int p) {
- tin[u] = t;
- up[u] = t++;
- used[u] = 1;
- int c = 0;
- for (auto i : v[u]) {
- if (i == p) continue;
- if (used[i]) {
- up[u] = min(tin[i], up[u]);
- } else {
- dfs(i, u);
- up[u] = min(up[u], up[i]);
- if (up[i] >= tin[u] && p != -1) {
- res.insert(u);
- }
- c++;
- }
- }
- if (p == -1 && c > 1) {
- res.insert(u);
- }
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0); cout.tie(0);
- // freopen("input.txt", "r", stdin);
- // freopen("output.txt", "w", stdout);
- cin >> n >> m;
- v.resize(n);
- used.resize(n);
- tin.resize(n);
- up.resize(n);
- for (int i=0; i < m; ++i) {
- int d1, d2;
- cin >> d1 >> d2;
- d2--; d1--;
- if (d1 > d2) swap(d1, d2);
- v[d1].push_back(d2);
- v[d2].push_back(d1);
- }
- for (int i=0; i < n; ++i) {
- if (!used[i]) {
- dfs(i, -1);
- }
- }
- cout << res.size() << '\n';
- for (auto i : res) cout << i + 1 << " ";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement