[9470번] Strahler 순서

문제 출처 :

https://www.acmicpc.net/problem/9470

알고리즘 분석 :

문제 해결에 필요한 사항

1. 위상 정렬 :: http://www.crocus.co.kr/716

이 문제의 핵심은 

1. 해당하는 정점에 존재하는 최댓값이 무엇인가?

2. 정점에 존재하는 그 최댓값이 총 몇개있는가?

이 두개가 가장 중요한 요소이다.

따라서 이것을 판별하기위해서는 getmax배열과 chk배열을 이용하여 정답을 찾아내면 된다.

아래 코드에 주석으로 설명해두었는데, line[next]가 0이 될 경우 그때의 최댓값이 총 몇개있었는지 확인하여

최댓값이 2개 이상이라면 +1을, 그게 아니라면 그 값을 그대로 넘겨주면 된다.

소스 코드 : 

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 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85

#include <iostream> #include <cstdio> #include <queue> #include <memory.h> #include <vector>   #define MAX_NODE 1001   using namespace std;   int line[MAX_NODE]; int chk[MAX_NODE][MAX_NODE]; // chk[i][j] :: i번 노드에 j의 개수가 몇개인가? int getmax[MAX_NODE]; // 현재 노드에 저장된 최대 값   int main() {     int tCase;     int tc, v, e;     scanf("%d", &tCase);       while (tCase--)     {         vector<int> vc[MAX_NODE];         memset(line, 0, sizeof(line));         memset(chk, 0, sizeof(chk));         memset(getmax, 0, sizeof(getmax));         scanf("%d %d %d", &tc, &v, &e);           for (int i = 0; i < e; i++)         {             int cur, prev;             scanf("%d %d", &prev, &cur);               line[cur]++;             vc[prev].push_back(cur);         }           queue<int> q;           for (int i = 1; i <= v; i++)             if (line[i] == 0)             {                 // 강의 근원은 1                 getmax[i] = 1;                 q.push(i);             }           // 위상 정렬         for (int i = 0; i < v; i++)         {             int cur = q.front();             q.pop();               for (int j = 0; j < vc[cur].size(); j++)             {                 int next = vc[cur][j];                   // next의 위치에 존재하는 최댓값 찾기                         getmax[next] = max(getmax[next], getmax[cur]);                 // next에 해당하는 개수를 + 1                 chk[next][getmax[next]]++;                   if (--line[next] == 0)                 {                     int tmp = getmax[next];                       // next에 tmp값의 개수가 2개 이상이면                     if (chk[next][tmp] >= 2)                         getmax[next] = getmax[cur] + 1;                     else                         getmax[next] = getmax[cur];                       q.push(next);                 }             }         }           printf("%d %d\n", tc, getmax[v]);     }       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus