9470

topological sort를 이용하면 별로 어렵지 않은 문제...

하지만 이 문제는 꽤 많은 시간을 허비했다

알고리즘 문제를 풀 때 자신이 유지하는 자료구조의 스펙을 정확히 해야한다.

내가 위 자료구조는 어떠한 값을 입력해둘 것인가를 확실히 해두어야 후에 스스로에게 헷갈리지 않는다.

머릿 속으로만 모두 해결하려 하지 말고 자신의 자료구조를 손으로 그려보는 것이 가장 좋은 방법일 것 같다.

#include<iostream> #include<cstdio> #include<vector> #include<queue> #include<algorithm> using namespace std; int indeg[1005]; int order[1005]; vector<int> orders[1005]; vector<int> edges[1005]; int main(){ int tc; int tc_num, node_num, edge_num; int from, to; int res; scanf("%d", &tc); queue<int> q; for(int clk=0; clk<tc; clk++){ scanf("%d %d %d", &tc_num, &node_num, &edge_num); for(int i=1; i<=node_num; i++){ edges[i].clear(); orders[i].clear(); indeg[i]=0; order[i]=0; res=0; } for(int cnt=0; cnt<edge_num; cnt++){ scanf("%d %d", &from, &to); edges[from].push_back(to); indeg[to]++; } for(int i=1; i<=node_num; i++) if(indeg[i]==0){ q.push(i); } while(!q.empty()){ int front = q.front(); q.pop(); if(orders[front].empty()) order[front]=1; else{ if(orders[front].size()==1) order[front]=orders[front].back(); else{ sort(orders[front].begin(), orders[front].end()); if(orders[front][orders[front].size()-1] == orders[front][orders[front].size()-2]) order[front]=orders[front].back()+1; else order[front]=orders[front].back(); } } res=max(res, order[front]); for(int i=0; i<edges[front].size(); i++){ indeg[edges[front][i]]--; orders[edges[front][i]].push_back(order[front]); if(indeg[edges[front][i]]==0) q.push(edges[front][i]); } } printf("%d %d\n", tc_num, res); } return 0; }