글 읽기 - 2458 키순서 질문이요

wnsqlehlswk 9년 전 0

파이썬 3 코드 입니다

그래프를 방향이 큰쪽으로 가는거랑 작은거로 가는 2개 만들고

각 정점에 대해 bfs 돌려 각각 두개의 그래프 에서 방문하는 정점의 수를

합해서 한게 정점의 갯수+1 이면 카운트 올려서 츨력했는데

틀렸다고 나와요 dfs 로 돌려도 그렇고

뭐가 잘못된 건 가요?

v=int(input())
e=int(input())
G1=[[]for i in range(v+1)]
G2=[[]for i in range(v+1)]

for i in range(e):
    a,b=map(int,input().split())
    G1[a]+=[b]
    G2[b]+=[a]

def dfs(G,start):

    ret=1
    for post in G[start]:
        if check[post]==0:
            check[post]=1
            ret+=dfs(G,post)
    return ret

def bfs(G,start):
    check=[0]*(v+1)
    q=[start]

    check[start]=1
    ret=1
    while len(q)>0:
        cur=q.pop()
        
        for post in G[cur]:
            if check[post]==1:
                continue
            q.append(post)
            check[post]=1
            ret+=1

    return ret

ans=0
for i in range(1,v+1):
    ##bfs 돌릴떄 
    #print (i,bfs(G1,i),bfs(G2,i))
    #if bfs(G1,i)+bfs(G2,i)==v-1:ans+=1
    
    #dfs 돌릴떄
    check=[0]*(v+1)
    a=dfs(G1,i)

    check=[0]*(v+1)
    b=dfs(G2,i)
    if a+b==v+1:ans+=1
print (ans)

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

문제

문제

출처

ICPC

2458 키순서 질문이요

wnsqlehlswk 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말