Advertisement
Guest User

Untitled

a guest
Apr 6th, 2020
151
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.26 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. vector<bool> visited;
  8. vector<int> tin, low, res;
  9. vector<vector<int>> G;
  10.  
  11. int timer;
  12.  
  13. void dfs_calc(int v, int parent = -1) {
  14.     visited[v] = true;
  15.     tin[v] = low[v] = timer++;
  16.     for (int x : G[v]) {
  17.         if (x == parent)
  18.             continue;
  19.         if (visited[x]) {
  20.             low[v] = min(low[v], tin[x]);
  21.         } else {
  22.             dfs_calc(x, v);
  23.             low[v] = min(low[v], low[x]);
  24.         }
  25.     }
  26. }
  27.  
  28. void dfs_find(int v) {
  29.     visited[v] = true;
  30.     for (int x : G[v]) {
  31.         if (tin[x] != low[x] && !visited[x]) {
  32.             res.push_back(x);
  33.             dfs_find(x);
  34.         }
  35.     }
  36. }
  37.  
  38. int main() {
  39.     int cdb, eldb, start, a, b;
  40.     cin >> cdb >> eldb >> start;
  41.     G.resize(cdb);
  42.     tin.resize(cdb);
  43.     low.resize(cdb);
  44.     visited.resize(cdb, false);
  45.     for (int i = 0; i < eldb; i++) {
  46.         cin >> a >> b;
  47.         G[a - 1].push_back(b - 1);
  48.         G[b - 1].push_back(a - 1);
  49.     }
  50.     dfs_calc(start-1);
  51.     fill(visited.begin(), visited.end(), false);
  52.     dfs_find(start-1);
  53.     cout << res.size()+1 << endl << start;
  54.     for (int x : res) {
  55.         cout << " " << x+1;
  56.     }
  57.     cout << endl;
  58.     return 0;
  59. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement