FilesExpand file tree

 master

/

6.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

68 lines (57 loc) · 2.29 KB

 master

/

6.java

Copy path

Top

File metadata and controls

• Code
• Blame

68 lines (57 loc) · 2.29 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

import java.util.*;

public class Main {

// 노드의 개수(V)와 간선의 개수(E)

// 노드의 개수는 최대 100,000개라고 가정

public static int v, e;

// 모든 노드에 대한 진입차수는 0으로 초기화

public static int[] indegree = new int[100001];

// 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화

public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

// 위상 정렬 함수

public static void topologySort() {

ArrayList<Integer> result = new ArrayList<>(); // 알고리즘 수행 결과를 담을 리스트

Queue<Integer> q = new LinkedList<>(); // 큐 라이브러리 사용

// 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입

for (int i = 1; i <= v; i++) {

if (indegree[i] == 0) {

q.offer(i);

}

}

// 큐가 빌 때까지 반복

while (!q.isEmpty()) {

// 큐에서 원소 꺼내기

int now = q.poll();

result.add(now);

// 해당 원소와 연결된 노드들의 진입차수에서 1 빼기

for (int i = 0; i < graph.get(now).size(); i++) {

indegree[graph.get(now).get(i)] -= 1;

// 새롭게 진입차수가 0이 되는 노드를 큐에 삽입

if (indegree[graph.get(now).get(i)] == 0) {

q.offer(graph.get(now).get(i));

}

}

}

// 위상 정렬을 수행한 결과 출력

for (int i = 0; i < result.size(); i++) {

System.out.print(result.get(i) + " ");

}

}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

v = sc.nextInt();

e = sc.nextInt();

// 그래프 초기화

for (int i = 0; i <= v; i++) {

graph.add(new ArrayList<Integer>());

}

// 방향 그래프의 모든 간선 정보를 입력 받기

for (int i = 0; i < e; i++) {

int a = sc.nextInt();

int b = sc.nextInt();

graph.get(a).add(b); // 정점 A에서 B로 이동 가능

// 진입 차수를 1 증가

indegree[b] += 1;

}

topologySort();

}

}