Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <string>
- #include <cstdio>
- #include <set>
- #include <map>
- #include <sstream>
- #include <iterator>
- #include <cmath>
- #include <unordered_map>
- #include <queue>
- using namespace std;
- void dfs(int u, int p, int dep, vector< vector<int> > &g,
- vector<int> &d, vector<int> &fup, vector<int> &dots){
- d[u] = fup[u] = dep;
- int sons = 0;
- bool isDot = false;
- for (int i = 0; i < g[u].size(); ++i){
- if(g[u][i] == p)
- continue;
- if(d[g[u][i]] >= 0)
- fup[u] = min(fup[u], d[g[u][i]]);
- else{
- dfs(g[u][i], u, dep + 1, g, d, fup, dots);
- fup[u] = min(fup[u], fup[g[u][i]]);
- if(u != p && fup[g[u][i]] >= d[u])
- isDot = true;
- sons++;
- }
- }
- if(u == p && sons > 1)
- isDot = true;
- if(isDot)
- dots.push_back(u);
- }
- int main(){
- ios_base::sync_with_stdio(false);
- int n, m;
- cin >> n >> m;
- vector< vector<int> > g(n);
- for (int i = 0; i < m; ++i){
- int x, y;
- cin >> x >> y;
- g[x - 1].push_back(y - 1);
- g[y - 1].push_back(x - 1);
- }
- vector<int> d(n, -1);
- vector<int> fup(n, -1);
- vector<int> dots;
- dfs(0, 0, 0, g, d, fup, dots);
- sort(dots.begin(), dots.end());
- cout << dots.size() << endl;
- for (int i = 0; i < dots.size(); ++i)
- cout << dots[i] + 1 << " ";
- cout << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement