글 읽기 - 돌멩이를 못줍고 있어요

alftjd1 4년 전 2

왜 안될까요

import sys
input = sys.stdin.readline
n, k = map(int,input().split())
graph = [[False] * (n+1) for _ in range(n+1)]
for _ in range(k):
    a, b = map(int,input().split())
    graph[a][b] = True

temp = [0] * (n+1)

def scanf(v,temp):
    if v == n+1:
        return 1
    if v in temp:
        v += 1
        return scanf(v,temp)
    for i in range(1,n+1):
        if graph[v][i]:
            if temp[i] == 0:
                graph[v][i] = False
                temp[i] = v
                v += 1
                return scanf(v,temp)

            elif temp[i] > 0:
                if any(graph[temp[i]]):
                    graph[v][i] = False
                    temp[i],v = v,temp[i]
                    return scanf(v,temp)
    v += 1
    return scanf(v,temp)

v = 1
scanf(v,temp)
print(len(list(filter(lambda x : x > 0,temp))))

'''
(성공했었던 예제)

5 8
1 1
2 2
4 4
5 5
1 3
2 3
4 3
5 3
    
x.x..
.xx..
.....
..xx.
..x.x

답은 4번

========

4 6
1 1
1 4
2 1 
2 3
3 1
3 2

x..x
x.x.
xx..
....

답은 3번

=======

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

..x..
...x.
.xxxx
..x..
..x..

답은 3번
'''

hello70825 4년 전 1

n=500, k=10000일 때 해당하는 랜덤한 값을 넣어보니 재귀깊이 오류가 나옵니다.

그래서 import sys 다음 줄에 sys.setlimitcursion(100000)을 추가해줘야합니다.

그리고 이것을 추가해도 시간 초과나 메모리 초과가 나올 것 같습니다.

글쓴이님이 푸신 문제들을 보니 아직 풀만한 문제는 아닙니다.

이 문제는 네트워크 플로우 문제중 이분 매칭을 다루는 문제입니다.

alftjd1 4년 전 1

알겠습니다

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

문제

문제

출처

ICPC

돌멩이를 못줍고 있어요

alftjd1 4년 전 2

hello70825 4년 전 1

alftjd1 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말