[백준] 2252. 줄 세우기

[문제]

 

www.acmicpc.net/problem/2252

2252번: 줄 세우기

[코드]

N 명의 학생들을 M번 비교하고 그 결과가 입력으로 주어진다.

이를 통해 학생들을 줄을 세우는 결과를 출력하면 된다.

 

학생들의 키가 모두 주어진 것이 아니고 일부만 주어졌으므로 '위상 정렬'을 사용해서 풀었다.

Degree에 각 노드에 대한 연결 차수를 저장하고

연결 차수가 0인 노드만 queue에 push 하여 순서대로 출력했다.

 

[풀이]

 

시간 : 44ms

 

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

#define MAX 32001

using namespace std;

int N,M;
int Degree[MAX]={0,};

vector <int> v[MAX];


int main(void)
{
    queue <int> q;
    
    scanf("%d %d",&N,&M);
    for(int i=0;i<M;i++)
    {
        int x1,x2;
        scanf("%d %d",&x1,&x2);
        
        Degree[x2]++;
        v[x1].push_back(x2);
    }
    
    for(int i=1;i<=N;i++)    if(Degree[i]==0)    q.push(i);
    
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        
        printf("%d ",x);
        
        for(int i=0;i<v[x].size();i++){
            int tmp = v[x][i];
            Degree[tmp]--;
            if(Degree[tmp]==0)  q.push(tmp);
        }
    }
    return 0;
}