위상 정렬 (Topology Sort)

그래프에 다양한 조건들이 얽혀있을 때, 조건에 부합하는 일직선의 경로를 찾는 알고리즘

특징

방향 그래프

여러개의 경로가 존재할 수 있음

사이클이 존재하지 않음

알고리즘 구조

1. 진입 차수가 0인 정점을 모두 큐에 삽입하기
2. 큐에서 정점을 꺼냄
   1. 꺼낸 순서가 위상정렬된 순서
3. 꺼낸 정점과 연결된 간선의 진입 차수를 1씩 빼기
4. 이후 다시 진입차수가 0이 된 정점을 큐에 삽입
5. 만약, V번 반복하기 전에 큐가 비어있다면 사이클이 발생한 것임

// 인접 행렬과 진입 차수 초기화
vector<vector<int>> adj(N + 1);
vector<int> inDegree(N + 1);
for (int i = 0; i < M; i++) {
    cin >> A >> B;
    adj[A].push_back(B);
    inDegree[B]++;
}

// 진입 차수가 0인 값을 큐에 넣기
vector<int> res(N + 1, 1);
for (int i = 1; i <= N; i++) {
    if (inDegree[i] == 0) {
        q.push(i);
    }
}

// 정점 개수만큼 반복
for (int i = 1; i <= N; i++) {
    if (q.empty()) continue;
    int cur = q.front(); // 큐에서 하나씩 제거
    q.pop();
		
		// 해당 정점을 삭제한다
    for (int j = 0; j < adj[cur].size(); j++) { // 현재 큐에 연결된 정점 탐색 
    int next = adj[cur][j];
    if (--inDegree[next] == 0) { // 다음 정점의 진입 차수를 1씩 뺴고, 0이면 큐에 넣기
        q.push(next);
    }
}