글 읽기 - 반례좀 찾아주세요 .. 굽신굽신

johyunkyum 1년 전 0

소스 코드는 이런데요. 위상정렬 이런거 생각 안하고 풀었는데 반례를 찾기가 어렵네요..

고수님들의 도움이 필요합니다. . .

from collections import defaultdict
import sys
import heapq
input = sys.stdin.readline

n, m = map(int, input().split())
visited = [False for i in range(n+1)]
arr = defaultdict(list)
result = []

for i in range(m):
    a, b = map(int, input().split())
    heapq.heappush(arr[b], a)


def solver(i, q, level):
    global visited

    if visited[i]:
        return q

    visited[i] = True

    for v in arr[i]:
        solver(v, q, level=level+1)

        if not visited[v]:
            q[level+1].append(v)

    q[level].append(i)

    return q


kk = dict()
for i in range(1, n+1):
    temp = []
    k = solver(i, defaultdict(list), 0)

    for key, value in sorted(k.items(), reverse=True):
        temp += sorted(value)

    kk[i] = temp

for k, v in sorted(kk.items(), key=lambda item: item[1]):
    if v:
        for i in v:
            print(i, end=' ')
"""
5 3
4 1
3 1
5 3
-> 5 3 4 1 2

5 4
5 4
4 3
3 2 
2 1
5 4 3 2 1


4 2
4 2
3 1
3 1 4 2

5 4
4 1
5 1
2 5 
3 5
2 3 4 5 1

6 7
5 6
5 2
2 4
4 3
2 1
6 1
1 3
4 3 5 2 6 1
"""

sasak2 1년 전 0

6 7

5 6

5 2

2 4

4 3

2 1

6 1

1 3

4 3 5 2 6 1

여기서 마지막 줄 때문에 1을 3보다 먼저 풀어야 하는데 3이 1보다 앞에 있으니까 틀린거 아닌가요

bsu1209 1년 전 1

5 3
4 1
3 1
5 3
-> 5 3 4 1 2

이 예시도 가능하면 쉬운 문제를 먼저 풀어야 하니,
선행 관계가 없는 2가 가장 먼저 오고,
4 또한 5 앞으로 올 수 있지 않을까요?

제 생각에는 정답이
2 4 5 3 1
인 것 같아요 ..!

wpekdl153 10달 전 0

맞아요....갑자기 혼동이 와서 뭐지 했네요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례좀 찾아주세요 .. 굽신굽신

johyunkyum 1년 전 0

sasak2 1년 전 0

bsu1209 1년 전 1

wpekdl153 10달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말