정렬이 아님 그래프임
solved.ac - 문제 › 태그 › topological_sorting
#include <stdio.h>
#include <queue>
#include <string.h> //memset
#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)); //memset() 배열 0으로 초기화
memset(wait,0,sizeof(wait));
scanf("%d %d",&N,&K);
for(int j=0;j<N;j++){
scanf("%d",&time[j+1]);
v[j+1].clear();
}
int t1,t2; // t1을 해야 t2를 할 수 있음
for(int j=0;j<K;j++){
scanf("%d %d",&t1,&t2);
v[t1].push_back(t2); //t1에 t2 넣어줌 (큐에서 사용)
comein[t2]++; // 선행 노드 수 +1
}
scanf("%d",&end);
for(int j=1;j<=N;j++){
if(comein[j]==0){
q.push(j); //선행차수0인 애들 넣기
}
}
while(!q.empty()){
int num = q.front(); //현재 위치
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]);
}
}
vector<int> v[1000];
1 → 2 3
2 → 4
3 → 4
4 →
1 2 3 4
[0 0 0 0 ] //이게 0이여야 실행할 수 있다.
빼면서
0이면 선행하는 게 없음 → 큐에 집어넣기
0이 아니면
선행해야하는게 아직남아있음 → 보류
큐 ) 1 → 2 → 3 →4