BOJ 26157 - 즉흥 여행 (Hard)

BOJ 26157 - 즉흥 여행 (Hard)

SCC 문제이지만, 문제에서 구하라는 조건이 처음 구한다면 꽤나 생각하기에 어렵다.

DAG가 linear한 form일 때의 source를 찾으라는 문제가 될 수 있는데,

여러가지 시도를 해보았고 각각 반례가 등장했다.

역간선들로 $degree_{out}$ 이 $0$인 친구들부터 돌려서 위상정렬

갈라지는 간선이 있을 수 있어서 안된다.

$degree_{in} > 1$ 나 $degree_{out} > 1$ 인 경우를 검사한다.

그래도 linear한 DAG가 될 수 있고, 반례는 다음과 같다.

• $1 \to 2$
• $1 \to 3$
• $2 \to 3$

$1 \to 2 \to 3$ 하면 된다.

뭐대충 어떻게 하다 맞았는데, 내 방법 말고 깔끔해보이는 피자사와님 코드를 첨부한다.

  // If DAG is linear, return its source.
  // Otherwise, return -1.
  int linear_dag_source() {
    queue<int> q;
    vector<int> indegree(scc_indegree);

    int o = -1;
    for (int i = 1; i <= scc_cnt; i++) {
      if (indegree[i] == 0) {
        q.push(i);
        o = i;
      }
    }

    while (!q.empty()) {
      if (q.size() > 1) return -1;

      int cur = q.front(); q.pop();
      for (int nxt : scc_graph[cur]) {
        if (--indegree[nxt] == 0) q.push(nxt);
      }
    }

    return o;
  }

핵심은 위상정렬을 하며 큐에 크기가 2 이상이 있을 때를 검출하는 것이다.

이런 방법으로 $degree_{in}=0$ 인 scc 가 여러개가 있는 경우나, 두 개의 방향으로 갈라지는 것을 모두 검출할 수 있다.