Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- int n, m, t;
- vector <vector <int>> G;
- vector <int> enter;
- vector <int> back;
- vector <bool> visited;
- vector <int> node;
- void dfs(int u, int p = 0){
- visited[u] = true;
- enter[u] = back[u] = t++;
- int c = 1;
- for (int i = 0; i < G[u].size(); i++){
- int v = G[u][i];
- if (v == p){
- continue;
- }
- if (visited[v]){
- back[u] = min(back[u], enter[v]);
- } else {
- dfs(v, u);
- back[u] = min(back[u], back[v]);
- if ((back[v] >= enter[u]) && (p != 0)){
- node.push_back(u);
- }
- ++c;
- }
- }
- if ((p == 0) && (c > 2)){
- node.push_back(u);
- }
- }
- int main() {
- int dep, dest;
- cin >> n >> m;
- G.resize(n+1);
- back.resize(n+1);
- enter.resize(n+1);
- visited.resize(n+1);
- t = 0;
- for (int i = 1; i <= m; i++){
- cin >> dep >> dest;
- G[dep].push_back(dest);
- G[dest].push_back(dep);
- }
- for (int i = 0; i <= n; i++){
- visited[i] = false;
- }
- for (int i = 1; i <= n; i++){
- if (!visited[i]) {
- dfs(i);
- }
- }
- cout << node.size() << endl;
- sort(node.begin(), node.end());
- if (! node.empty()) {
- cout << node[0] << " ";
- for (int i = 1; i < node.size(); i++) {
- if (node[i-1] != node[i])
- cout << node[i] << " ";
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement