fork download
copy 
  1.  
  2. #include <iostream>
  3. #include <vector>
  4. #include <stack>
  5. using namespace std;
  6.  
  7. int MAX_N = 10005;
  8.  
  9. vector<int> adj[10005];
  10. int V ,E, found[10005], cut[10005];    // 발견된 순서
  11. int counter = 0;
  12.  
  13. // here : 현재 탐색중인 위치
  14. // return 현재 탐색중인 노드를 루트로 하는 sub graph가 방문할 수 있는
  15. // 최상위 위치(=발견 순서의 최솟값)
  16. int dfs(int here, int is_root) {
  17.     found[here] = ++counter;    // 발견 순서 저장
  18.  
  19.     int low = found[here];
  20.     int next, child = 0;
  21.     for (int i = 0; i < (int)adj[here].size(); ++i) {
  22.         next = adj[here][i];
  23.  
  24.         if (found[next] == 0) {     // 미방문 노드
  25.             ++child;
  26.             int sub = dfs(next, false);
  27.  
  28.             if (!is_root && sub >= found[here]) {   // 단절점 조건
  29.                 cut[here] = true;
  30.             }
  31.             if (sub < low) low = sub;   // low 갱신
  32.         } else {        // 이미 방문한 노드
  33.             if (found[next] < low) {
  34.                 low = found[next];
  35.             }
  36.         }
  37.     }
  38.  
  39.     // root 노드에 대한 별도 처리
  40.     if (is_root && child >= 2) cut[here] = true;
  41.  
  42.     return low;
  43. }
  44.  
  45. int main() {
  46.  
  47.     scanf("%d %d", &V , &E);
  48.  
  49.     for (int i = 0 ; i < E ; i ++){
  50.         int a,b;
  51.         scanf("%d %d", &a,&b);
  52.         adj[a].push_back(b);
  53.         adj[b].push_back(a);
  54.     }
  55.  
  56.     while(1){
  57.     	int start=-1;
  58.         for (int i =1  ; i <= V ; i++) {
  59.             if ( found[i] == 0 ) {
  60.                 start= i;
  61.                 break;
  62.             }
  63.         }
  64.         if ( start == -1) break;
  65.  
  66.         if (start == 1 ) dfs(start,1);
  67.         else dfs(start,0);
  68.  
  69.     }
  70.  
  71.     int cut_count=0;
  72.     for (int i =1  ; i <= V ; i++){
  73.     	if(cut[i]== true ) cut_count++;
  74.     }
  75.     cout << cut_count << "\n";
  76.      for (int i =1  ; i <= V ; i++){
  77.     	if(cut[i]== true ) cout << i << " ";
  78.     }
  79.  
  80.     return 0;
  81. }
Success #stdin #stdout 0s 15552KB
comments (?)
stdin
copy 
7 8
1 4
1 4
4 5
5 1
1 6
6 7
2 7
7 3
stdout
copy 
3
1 6 7
https://ideone.com/mNyekV
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!