[C++] 2252번 줄 세우기 - 위상 정렬

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

#define LOOP(i, N) for(int i=1; i<=N; i++)

#define MAX_M 100010
#define MAX_N 32001

using namespace std;

int N, M;  //학생의 수 N, 키를 비교한 회수 M
vector<int> r[MAX_M];  //키 비교한 것 저장
int inDegree[MAX_N];  //진입 차수
int res[MAX_N];  //위상 정렬 결과

void input()
{
    cin >> N >> M;
    int x, y;
    LOOP(i, M) {
        cin >> x >> y;
        r[x].push_back(y);
        inDegree[y]++;
    }
}

void topologySort()
{
    queue<int> q;
    
    LOOP(i, N) {
        if(!inDegree[i]) q.push(i);
    }
    
    while(!q.empty()) {
        int x = q.front(); q.pop();
        cout << x << ' ';
        for(int j=0; j<r[x].size(); j++) {
            int y = r[x][j];
            if(!(--inDegree[y])) q.push(y);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    input();
    
    topologySort();
    
    return 0;
}

그냥 간단한 위상 정렬 문제다.

 

https://leyamon.tistory.com/entry/C-1005%EB%B2%88-ACM-Craft-DP-%EC%9C%84%EC%83%81-%EC%A0%95%EB%A0%AC-DFS

[C++] 1005번 ACM Craft - DP, 위상 정렬, DFS

 

ACM Craft문제랑 거의 똑같아서 코드 복사 붙여넣기 해도 AC나온다.

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.