fork download
copy 
  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <cstdio>
  7. #include <set>
  8. using namespace std;
  9. const int MAXN =1000;
  10. vector<int> g[MAXN];
  11. bool used[MAXN];
  12. int timer, tin[MAXN], fup[MAXN];
  13. set<int> s;
  14.  
  15. void dfs (int v, int p = -1) {
  16.  used[v] = true;
  17.  tin[v] = fup[v] = timer++;
  18.  int children = 0;
  19.  for (size_t i=0; i<g[v].size(); ++i) {
  20.   int to = g[v][i];
  21.   if (used[to])
  22.    fup[v] = min (fup[v], tin[to]);
  23.   else {
  24.    dfs (to, v);
  25.    fup[v] = min (fup[v], fup[to]);
  26.    if (fup[to] >= tin[v] && p != -1)
  27.     s.insert(v + 1);
  28.    ++children;
  29.   }
  30.  }
  31.  if (p == -1 && children > 1)
  32.   s.insert(v + 1);
  33. }
  34.  
  35. int main() {
  36.  
  37.  int n,a,b, m;
  38.  //freopen("points.in", "r", stdin);
  39.  //freopen("points.out", "W", stdout);
  40.  cin>>n >> m;
  41.  for (int i = 0; i < m; i++)
  42.  {
  43.   cin >> a>>b;
  44.   a--;
  45.   b--;
  46.   g[b].push_back(a);
  47.   g[a].push_back(b);
  48.  }
  49.  
  50.  timer = 0;
  51.  for (int i=0; i<n; ++i)
  52.   used[i] = false;
  53.  dfs (0);
  54.  cout << s.size() << endl;
  55.  for(auto i = s.begin(); i != s.end(); ++i){
  56.   cout << *i<<"\n";
  57.  }
  58. }
Success #stdin #stdout 0s 15272KB
comments (?)
stdin
copy 
9 12
1 2
2 3
4 5
2 6
2 7
8 9
1 3
1 4
1 5
6 7
3 8
3 9
stdout
copy 
3
1
2
3
https://ideone.com/mFUO6K
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!