2252번: 줄 세우기

2252번: 줄 세우기

사용 언어: C++

 

풀이

위상 정렬 문제. 학생 1이 3보다 앞에 있어야 하면 AddEdge(1, 3)에 넣어서 G[1].push_back(3)으로 방향을 나타내고, In[3]++로 학생 3은 진입 차수가 증가해 자기보다 앞선 사람이 있다고 마킹해두는 것.
큐에 TopSort()로 진입차수가 0인 사람은 다 push해서 자기 이전에 오는 사람이 없으므로 바로 출력. 그 사람을 출력했으면 그 사람과 연결된 남은 사람들은 진입차수가 1 감소하므로 1을 빼주고, 뺐는데 진입차수가 0이되면 다시 큐에 넣어서 더 이상 남은 사람이 없을때까지 진행.

#include <bits/stdc++.h>

using namespace std;

int In[100010];
vector<int> G[100010];
int N, M;

void AddEdge(int s, int e) { G[s].push_back(e); In[e]++; }

void TopSort()
{
    queue<int> Q;
    for(int i=1; i<=N; i++)
    {
        // 진입차수가 0이면 앞에 아무도 안 오므로 출력 (큐에 넣기)
        if(!In[i]) Q.push(i);
    }
    while(!Q.empty())
    {
        int v = Q.front(); Q.pop();
        cout << v << " ";
        for(auto i : G[v])
        {
            // 방금 출력을 해서 뺐으므로 1을 뺌. 뺀 후 진입차수가 0이면 큐에 push
            if(!--In[i])
            {
                Q.push(i);
            }
        }

    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;

    for(int i=0; i<M; i++)
    {
        int s, e;
        cin >> s >> e;
        AddEdge(s, e);
    }

    TopSort();

    return 0;
}