Advertisement
Guest User

Untitled

a guest
Apr 7th, 2020
286
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.31 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. vector<vector<int>> g;
  6. vector<bool> visited;
  7. vector<bool> double_enter;
  8. int double_count = 0;
  9.  
  10. /*void dfs(int v, int prev) {
  11.     visited[v] = true;
  12.     for (int u : g[v]) {
  13.         if (!visited[u]){
  14.             dfs(u,v);
  15.             if(double_enter[u]){double_enter[v]=true;}
  16.         }else{
  17.             if(double_enter[u] && u!=prev){
  18.                 double_enter[v]=true;
  19.             }
  20.         }
  21.     }
  22.     if(double_enter[v]){
  23.         double_count+=1;
  24.     }
  25. }*/
  26.  
  27. /*void dfs(int v, int prev) {
  28.     visited[v] = true;
  29.     for (int u : g[v]) {
  30.         if(visited[u]){
  31.             if(double_enter[u] && u!=prev){
  32.                 double_enter[v]=true;
  33.             }
  34.         }
  35.     }
  36.     for (int u : g[v]) {
  37.         if (!visited[u]){
  38.             dfs(u,v);
  39.             if(double_enter[u]){double_enter[v]=true;}
  40.         }
  41.     }
  42.     if(double_enter[v]){
  43.         double_count+=1;
  44.     }
  45. }*/
  46.  
  47. /*void dfs(int v, int prev) {
  48.     visited[v] = true;
  49.     for (int u = 0; u<g[v].size();++u) {
  50.         if (!visited[g[v][u]]){
  51.             dfs(g[v][u],v);
  52.             if(double_enter[g[v][u]]){double_enter[v]=true;}
  53.         }else{
  54.             if(double_enter[g[v][u]] && g[v][u]!=prev){
  55.                 double_enter[v]=true;
  56.             }
  57.         }
  58.     }
  59.     if(!double_enter[v]){
  60.         for (int u = g[v].size()-1;u>-1;--u) {
  61.             if (!visited[g[v][u]]){
  62.                 dfs(g[v][u],v);
  63.                 if(double_enter[g[v][u]]){double_enter[v]=true;}
  64.             }else{
  65.                 if(double_enter[g[v][u]] && g[v][u]!=prev){
  66.                     double_enter[v]=true;
  67.                 }
  68.             }
  69.         }
  70.     }
  71.     if(double_enter[v]){
  72.         double_count+=1;
  73.     }
  74. }*/
  75.  
  76. int main(){
  77.     int n,m,s;
  78.     cin>>n>>m>>s;
  79.     g.resize(n);
  80.     double_enter.resize(n);
  81.     visited.resize(n);
  82.     for(int i=0;i<m;++i){
  83.         int a,b;
  84.         cin>>a>>b;
  85.         g[a-1].push_back(b-1);
  86.         g[b-1].push_back(a-1);
  87.     }
  88.     double_enter[s-1]=true;
  89.     dfs(s-1,-1);
  90.     cout<<"\n"<<double_count<<"\n";
  91.     for(int i=0;i<n;++i){
  92.         if(double_enter[i]){
  93.             cout<<i+1<<" ";
  94.         }
  95.     }
  96.  
  97.     return 0;
  98. }
  99.  
  100. /*
  101. 11 12 3
  102. 3 2
  103. 2 4
  104. 4 3
  105. 1 3
  106. 2 6
  107. 6 10
  108. 6 11
  109. 2 11
  110. 5 7
  111. 5 8
  112. 5 4
  113. 7 8
  114.  
  115. 5
  116. 3 2 4 6 11
  117. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement