위상정렬

위상정렬이란?

순서가 정해져 있는 작업을 차례로 수행해야 할 때 사용하는 순서 결정 알고리즘!

그래프에 사이클이 존재한다면.. 위상정렬 수행이 불가능함..
(순서 정하는 것 자체가 불가능하기 때문!)

위의 그림과 같이 한가지 흐름으로 정리가 가능해야 함

위상정렬 구현 방법

1. 진입 노드 수를 정리해 둠
2. 진입 노드 수가 0인 정점 큐에 넣음
   진입노드 수가 0이면 출발지라는 뜻임..!
3. 연결된 간선 제거하고 연결된 새로운 정점 큐에 집어넣어줌

반복한다..!

예시문제

백준 1005
특정 노드 완료 시간 구하기...
노드 방문하면서 그 노드로 오는 데 걸리는 최대 시간을 저장하고 이를 이용해서 가장 오래 걸리는 시간만 저장한다..!

#include <stdio.h>
#include <queue>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
vector<int> v[1001];
queue<int> q;
int time[1001];

int comein[1001];
int wait[1001];

int main(){
	int n;
	scanf("%d",&n);
	
	for(int i=0;i<n;i++){
		int N,K=0;
		int end; 
		memset(comein,0,sizeof(comein));
		
		//printf("%d..",comein[1]);
		memset(wait,0,sizeof(wait));
		
		
		scanf("%d %d",&N,&K);
		//printf("%d %d\n\n",N,K);
		for(int j=0;j<N;j++){
			scanf("%d",&time[j+1]);
			v[j+1].clear();
		}
		int t1,t2;
		for(int j=0;j<K;j++){
			scanf("%d %d",&t1,&t2);
			v[t1].push_back(t2);
			comein[t2]++;
			
		}
		scanf("%d",&end);
		for(int j=1;j<=N;j++){
			//printf("%d.. %d\n",j,comein[j]);
			if(comein[j]==0){
				q.push(j);
				
			}
		}
		while(!q.empty()){
			int num = q.front();
			//printf("%d!",num);
			int sum = wait[num]+ time[num];
			{
			 
					for(int j=0;j<v[num].size();j++){
						int next = v[num][j];
						if(wait[next] < sum){
							wait[next] = sum;
						}
						if(--comein[next]==0){ // 일 시작해도 되는 노드! 
							//printf("%d?",comein[next]);
							q.push(next);
						}
					}
				
			}	
			
			q.pop();
		}
		printf("%d\n",wait[end]+ time[end]);
	}
}