Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- vector<vector<pair<int, int>>> g;
- vector<bool> used;
- vector<int> tin;
- vector<int> tup;
- int timer = 0;
- set<int> ans;
- vector<int> cnt;
- void dfs(int v, int ind) {
- used[v] = 1;
- tin[v] = timer++;
- tup[v] = tin[v];
- int ch = 0;
- for(int i = 0; i < g[v].size(); i++) {
- int to = g[v][i].first;
- if(g[v][i].second == ind) continue;
- if(!used[to]) { // прямое
- dfs(to, g[v][i].second);
- tup[v] = min(tup[v], tup[to]);
- ch++;
- if(tin[v] <= tup[to]) {
- ans.insert(v);
- }
- cnt[v]++;
- }
- else { // обратное
- tup[v] = min(tup[v], tin[to]);
- }
- }
- }
- int main() {
- int n, m;
- cin >> n >> m;
- g.resize(n);
- tin.resize(n);
- tup.resize(n);
- used.resize(n);
- cnt.resize(n);
- for(int i = 0; i < m; i++) {
- int a, b;
- cin >> a >> b;
- if(a > b) {
- swap(a, b);
- }
- a--;
- b--;
- g[a].push_back({b, i});
- g[b].push_back({a, i});
- }
- for(int i = 0; i < n; i++) {
- if(!used[i]) {
- dfs(i, i);
- }
- }
- cout << ans.size() - (cnt[0] < 2) << '\n';
- for(auto i : ans) {
- if(i == 0 && cnt[0] < 2) continue;
- cout << i + 1 << ' ';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement