Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <array>
- #include <vector>
- #include <numeric>
- #include <random>
- #include <chrono>
- #include <set>
- #include <map>
- #define int long long
- using namespace std;
- const long long INF = 1e9 + 7;
- const int MAXN = 2e4 + 1000;
- const int N = 1e5 + 10;
- vector<vector<pair<int, int>>> g;
- array<int, MAXN> used, tin, up;
- int timer = 0;
- set<int> ans;
- void dfs(int v, int e = -1) {
- used[v] = true;
- tin[v] = up[v] = timer++;
- int child = 0;
- for (auto [to, num]: g[v]) {
- if (num == e) {
- continue;
- }
- if (used[to]) {
- up[v] = min(up[v], tin[to]);
- } else {
- dfs(to, num);
- up[v] = min(up[v], up[to]);
- if (up[to] >= tin[v] && e != -1) {
- ans.insert(v);
- }
- ++child;
- }
- }
- if (e == -1 && child > 1) {
- ans.insert(v);
- }
- }
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- int n, m;
- cin >> n >> m;
- g.resize(n);
- for (int i = 0; i < m; ++i) {
- int u, v;
- cin >> u >> v;
- --u, --v;
- g[u].emplace_back(v, i);
- g[v].emplace_back(u, i);
- }
- for (int i = 0; i < n; ++i) {
- if (!used[i]) {
- dfs(i);
- }
- }
- cout << ans.size() << '\n';
- for (auto& i: ans) {
- cout << i + 1 << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment