코딩테스트준비/다시볼문제
백준 2252. 줄 세우기 (위상정렬)
haeullee
2023. 8. 15. 10:59
https://www.acmicpc.net/problem/2252
2252번: 줄 세우기
첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의
www.acmicpc.net
1. 특징
1) 위상정렬: 방향 그래프에서 간선이 주어진 정점 간 선후관계를 위배하지 않도록 나열하는 정렬 (사이클이 없는 방향 그래프에서만 잘 정의됨)
2. 구현 방식
1) 각 정점으로 들어오는 간선의 개수를 deg배열에 저장함.
int deg[]; //각 정점의 indegree 수
2) deg[i]가 0이 되는 정점은 queue에 삽입
3) queue가 empty가 될 때까지, queue의 front값을 pop하고, 그 정점의 인접 정점의 deg를 -1 해줌.
인접정점의 deg가 0이면, queue에 삽입.
3. 코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m;
int u, v;
vector<int> adj[32004];
int deg[32004]; //각 정점의 indegree
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i = 0; i < m; i++)
{
cin >> u >> v;
adj[u].push_back(v);
deg[v]++;
}
queue<int> q;
for(int i = 1; i <= n; i++)
{
if(deg[i] == 0) q.push(i);
}
while(!q.empty())
{
int cur = q.front(); q.pop();
cout << cur << ' ';
for(int nxt:adj[cur])
{
deg[nxt]--;
if(deg[nxt] == 0) q.push(nxt);
}
}
}