boj 11266: 단절점

https://www.acmicpc.net/problem/11266

11266번: 단절점

dfs를 실행하며 방문노드 순서를 매기며, (즉 discovered[here]보다 값이 작으면 here보다 먼저 방문한 셈이다.) 만약 here에서 방문안한 서브트리에서 인접한 노드가 here보다 조상이면, here는 단절점이 아니다. (그 이외엔 here는 단절점이다.)

혹은 here에서 방문안한 서브트리의 갯수가 두개 이상인데, 지금 here가 root라면, here는 단절점이다. 

ret 변수는 here에서 인접한 노드중 가장 조상을 저장하기 위한 변수라 볼 수 있다.

 

#include<bits/stdc++.h>
#define MAX 10000000
using namespace std;

int v,e,x,y,discovered[10001],counter=0;
set<int> ans;
vector<int> adj[10001];

int proc(int here, bool root){
  int len=adj[here].size(), child=0;
  discovered[here] = counter++;
  int ret = discovered[here];
  for(int i=0;i<len;i++){
    int next = adj[here][i];
    if(discovered[next]==-1){
      child++;
      int subret = proc(next,false);
      if(!root && subret>=discovered[here]){
        ans.insert(here);
      }
      ret = min(ret,subret);
    }else{
      ret = min(ret,discovered[next]);
    }
  }
  if(root && child>=2) ans.insert(here);
  return ret;
}


int main(){

  memset(discovered,-1,sizeof(discovered));
  cin>>v>>e;
  for(int i=0;i<e;i++){
      cin>>x>>y;
      adj[x].push_back(y);
      adj[y].push_back(x);
  }
  for(int i=1;i<=v;i++)
    if(discovered[i]==-1)
      proc(i,true);
  cout<<ans.size()<<'\n';
  if(ans.size()){

      for(auto &p: ans) cout<<p<<" ";
  }


  return 0;
}