728x90
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
심플하게 위상 정렬을 수행하는 문제
위상 정렬에 대한 설명은 아래의 포스트를 참조
https://jiuge-meogari-ps.tistory.com/14
위상 정렬(Topological Sort)
위상 정렬(topological sort)은 G가 간선 (u,v)를 가질 때 u가 v보다 순서상으로 먼저 나타나도록 모든 정점을 선형으로 나열하는 것이다. 여기서 만약 그래프가 순환을 가진다면 선형 나열은 불가능하
jiuge-meogari-ps.tistory.com
코드
|
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
|
#include <bits/stdc++.h>
using namespace std;
vector<int>vi[32003];
stack<int>s;
bool v[32003];
void dfs(int i){
for(int j=0;j<(int)vi[i].size();j++){
if(v[vi[i][j]])continue;
v[vi[i][j]]=true;
dfs(vi[i][j]);
s.push(vi[i][j]);
}
}
int main(){
int N,M,A,B;
scanf("%d%d",&N,&M);
for(int i=1;i<=M;i++){
scanf("%d%d",&A,&B);
vi[A].push_back(B);
}
for(int i=1;i<=N;i++){
if(v[i])continue;
v[i]=true;
dfs(i);
s.push(i);
}
while(!s.empty()){
printf("%d ",s.top());
s.pop();
}
return 0;
}
|
cs |
728x90
'BAEKJOON' 카테고리의 다른 글
| BAEKJOON 1005번: ACM Craft (0) | 2022.03.01 |
|---|---|
| BAEKJOON 1701번: Cubeditor (0) | 2022.03.01 |
| BAEKJOON 8913번: 문자열 뽑기 (0) | 2022.02.26 |
| BAEKJOON 9002번: Match Maker (0) | 2022.02.23 |
| BAEKJOON 22345번: 누적거리 (0) | 2022.02.09 |