음악프로그램

Problme link: https://www.acmicpc.net/problem/2623

간단한 위상정렬 문제로 볼 수 있다.

각 가수를 그래프의 정점으로, 인접한 두 순서를 간선으로 표현한다면 입력은 그래프로 표현될 수 있다.

그래프의 순서를 유지하는 위상정렬 결과를 아무거나 하나 출력해주면 된다.

주의할 점으로는 아래의 것들이 있을 수 있다.

• 입력이 꼭 하나의 그래프로 표현되지 않을 수도 있다(2개 이상의 세그먼트)
• 사이클을 이루는지의 판단이 필요하다(불가능한 경우 판별을 위해)
  • 방향성 그래프에서 사이클 유무는 아래와 같이 간단하게 알 수 있다.
  • DFS를 수행하면서,
  • 인접한 정점이 이미 방문상태인데,
  • 그 정점의 DFS가 완료되지 않았다.

#include <cstdio>
#include <vector>

using namespace std;

int N;
int M;
vector<bool> V;
vector<bool> F;
vector<vector<int> > G;

bool DoDfs(int here, vector<int>& topology)
{
  V[here] = true;
  for (const auto& there : G[here])
  {
    if (!V[there])
    {
      if (!DoDfs(there, topology))
      {
        return false;
      }
    }
    else if (!F[there])
    {
      return false;
    }
  }

  topology.emplace_back(here);
  F[here] = true;
  return true;
}

void Solve()
{
  vector<int> answer;
  for (int singer = 1; singer <= N; ++singer)
  {
    if (!V[singer] && !DoDfs(singer, answer))
    {
      printf("%d\n", 0);
    }
  }

  for (auto it = answer.rbegin(); it != answer.rend(); ++it)
  {
    printf("%d\n", *it);
  }

  return;
}

int main(void)
{
  // Read input
  scanf(" %d %d", &N, &M);
  V.assign(N + 1, false);
  F.assign(N + 1, false);
  G.assign(N + 1, vector<int>());
  for (int pd = 0; pd < M; ++pd)
  {
    int num_of_singers;
    int predecessor;
    int successor;
    scanf(" %d %d", &num_of_singers, &predecessor);

    for (int singer = 1; singer < num_of_singers; ++singer)
    {
      scanf(" %d", &successor);
      G[predecessor].emplace_back(successor);
      predecessor = successor;
    }
  }

  // Solve
  Solve();

  return 0;
}