https://jyj98020.tistory.com/m/282
이거 위상정렬시키면 안됨?
각 노드의 값이 초기에 1이라하고
node=q에서 꺼내기
n이 node에서 탐색가능하다하면
노드n의값=노드n의값+노드node의값
역방향 그래프도 같은 동작 수행
만약 특정노드에서 정방향에서 탐색한 노드값+역방향에서 탐색한 노드값이 노드의수-1이라면 순위결정가능
난 이풀이 생각났는데 반례있음?
이거 위상정렬시키면 안됨?
각 노드의 값이 초기에 1이라하고
node=q에서 꺼내기
n이 node에서 탐색가능하다하면
노드n의값=노드n의값+노드node의값
역방향 그래프도 같은 동작 수행
만약 특정노드에서 정방향에서 탐색한 노드값+역방향에서 탐색한 노드값이 노드의수-1이라면 순위결정가능
난 이풀이 생각났는데 반례있음?
이거 USACO 문제가 원본인데 그거 해설도 플로이드 씀
나도 다익스트라 플로이드 예제 돌아다니다 저건 다르게 풀 수 있을거같아서..
Input에서 사이클을 형성하게 줄 수도 있으려나? 만약 그렇다면 사이클을 형성하는 노드끼린 아예 논리상 맞지않는데 (1번이 2번보다 낮고 2번이 3번보다낮고 3번이 1번보다 낮다?)..
위상정렬하면 되기는 하는데 각 정점에서 도달할 수 있는 정점의 개수를 구하는 과정을 "노드n의값=노드n의값+노드node의값"처럼 할 수는 없음 위상정렬하면 시간복잡도 O(NM)에 할 수 있을 듯
boj.kr/2458 이거 말하는거 같은데, 이건 그냥 dfs N번 돌리는걸게 보통 풀이임 ㅇㅇ 게이 풀이의 반례로는, 1-> 2, 1 -> 3, 2 -> 4, 3 -> 4 하면 4번에 4가 아니라 5가 쌓임. (1이 2번 세짐)