반응형
문제
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) 접근 사고
2) 시간 복잡도
3) 배운 점
4) PS
정답 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
using namespace std;
const int MAX = 32001;
int indegree[MAX];
vector<int> edge[MAX];
int main(void)
{
fastio;
int n , m;
cin >> n >>m;
for(int i = 0; i < m ; i++)
{
int a, b;
cin >> a >> b;
indegree[b]++;
edge[a].push_back(b);
}
queue<int> q;
int ret[MAX];
for(int i =1; i <= n; i++)
if(indegree[i] == 0)
q.push(i);
for (int i = 0; i < n; i++)
{
if (q.empty())
break;
int cur = q.front();
q.pop();
ret[i] = cur;
for(auto idx : edge[cur])
{
if(--indegree[idx] == 0)
q.push(idx);
}
}
for(int i = 0; i < n; i++)
cout << ret[i] << " ";
}
|
cs |
반응형
'백준문제풀이 > TopologicalSort' 카테고리의 다른 글
| 1516번-게임개발 (0) | 2021.08.20 |
|---|