[Codeforces 919D]Substring
[Codeforces 919D]Substring - 1700 문제 설명 : directed edge로 구성된 그래프가 있다. 그래프의 각 노드에는 알파벳이 배정되어있다. 그래프의 경로를 지나면서 거쳐가는 노드들의 알파벳중에서 최대 빈도수를 구하는 문제이다. 무수히 많은 빈도수가 나올 때는 -1을 출력한다. 풀이 : 일단 그래프에서 사이클이 존재하는 경우 사이클 내에 있는 알파벳은 무수히 많이 등장할 수 있으므로 -1을 출력하면 된다. 만약 사이클이 없는게 확인된 그래프라면 위상정렬 알고리즘을 사용한다. 각 노드는 각 알파벳이 최대 몇 번 등장할 수 있는지 저장할 수 있는 freq[][]배열을 만든다. 그래서 다음 노드(next)에서 freq배열은 현재 노드의 freq배열과 같은 값을 가지면서, 다음 노드..
Problem Solving/Topological Sort
2019. 5. 23. 01:44