[swexpert] 1267. 작업순서 (C++, 위상정렬, dfs) [D6]

a -> b 방향으로 화살표가 있다면 a가 작업된 후에 b를 작업할 수 있다는 이야기

edge[a]에는 b를 추가해주고 cnt[b]는 1증가시킨다. (b로 들어오는 간선개수라고 생각해준다)

 

사전작업(간선)이 없는 곳, 즉 cnt[해당작업번호]=0인 곳부터 출력해준다.

dfs의 경우는 방문 배열 처리를 해준다. bfs는 0인 곳을 큐에 먼저 다 넣어줄 수 있어서 필요없다.

 

현재 방문한 곳 cur와 연결된 곳의 간선의 수를 하나 줄여주고 (사전작업이 하나 줄었으니까!)

연결된 곳의 cnt[다음정점번호]가 0이 된다면 방문할 수 있다.

 

#define _CRT_SECURE_NO_DEPRECATE
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

int v, e;
vector<int> edge[1001];
bool visit[1001];
int cnt[1001];

void dfs(int cur) {
	cout << cur << " ";
	visit[cur] = true;
	for (int i = 0; i < edge[cur].size(); i++) {
		int next = edge[cur].at(i);
		cnt[next]--;
		if (cnt[next] == 0) {//선행작업 없어진 후에야 한다.
			dfs(next);
		}
	}
}

int main(void) {

	ios::sync_with_stdio(false);
	cin.tie(NULL);


	for (int tc = 1; tc <= 10; tc++)
	{
		fill(cnt, cnt + 1001, 0);
		memset(visit, false, 1001);
		for (int i = 0; i < 1001; i++) {
			edge[i].clear();
		}
		
		cin >> v >> e;
		for (int i = 0; i < e; i++) {
			int a, b;
			cin >> a >> b;
			edge[a].push_back(b);
			cnt[b]++;
		}
		cout << "#" << tc << " ";
		for (int i = 1; i <= v; i++) {
			if (cnt[i] == 0 && visit[i]==false) {
				dfs(i);
			}
		}
		cout << "\n";
	}


	return 0;
}