[2668] 숫자고르기

 

2668번: 숫자고르기

아이디어

숫자들을 정점으로 생각하면 뽑은 숫자들의 집합이 일치한다 => 사이클이 있다고 볼 수 있다.

 

사이클을 검출하는 방법 : DFS

DFS를 돌다가 DFS가 아직 다 돌지않은 정점을 만나게 되면 사이클이 있다고 생각할 수 있다.

(다만 방문여부와는 별개로 생각해줘야한다. 처음 방문하는 정점도 DFS를 다 돌진 않은 상태니까)

DFS를 돌면서 자신이 이전에 방문한 정점을 저장해준다면 DFS가 다 안돈 정점부터

차례대로 자기 자신을 만날 때 까지 정답배열에 넣어주면 답을 구할 수 있다.

void dfs(int cur){
  if(vis[cur]){
    // 만약 방문한 적이 있지만 해당 정점이 DFS를 다 돈 상황이라면 더 들어가주지 않아도된다.
    if(fin[cur]) return;
    else{
      // 하지만 해당 방문한 적이 있지만 DFS를 다 안돌았다면 onCase라는 것이다.
      // 해당 정점부터 정답에 넣어주고 현재 정점이 나올 때까지 정점들을 넣어준다.
      ans.push_back(cur);
      int i=par[cur];
      while(i!=cur){
        ans.push_back(i);
        i=par[i];
      }
      return;
    }
  }
  vis[cur]=1;
  for(auto i:adj[cur]){
    if(!fin[i]){
      par[i]=cur;
      dfs(i);
    }
  }
  // *DFS가 끝났다는 것을 반드시 써주자*
  fin[cur]=1;
}