글 읽기 - SCC 어디가 틀렸는지 모르겠습니다 ㅠㅠ

kibum1024 1년 전 0

9%에서 틀렸다고 나옵니다ㅠㅠ

DFS 도 잘 되고 제가 본 테케에서는 전부 잘 맞습니다 ㅠㅠ

어디서 문제가 생긴건지 알려주시면 정말 감사드리겠습니다 ㅠㅠ

def dfs_list(N, adj_list):
    fintime = []
    stack = []
    visited = [False]*(N+1)
    for idx in range(1,N+1):
        if visited[idx]: continue
        stack.append(idx)
        visited[idx] = True
        while stack:
            x, noadj = stack[-1], True
            for j in adj_list[x]:
                if visited[j]==False:
                    stack.append(j)
                    visited[j] = True
                    noadj = False
            if noadj:
                fintime.append(stack.pop())
    fintime.reverse()
    return fintime

def rev_dfs_list(N,adj_list,fintime):
    visited = [False]*(N+1)
    scc_set = []
    stack = []
    for idx in fintime:
        if visited[idx]: continue
        scc, stack, visited[idx] = [], [idx], True
        while stack:
            x = stack.pop()
            scc.append(x)
            for j in adj_list[x]:
                if visited[j]==False:
                    stack.append(j)
                    visited[j] = True
        scc_set.append(scc)
    return scc_set

def data_output(scc_set):
    for scc in scc_set:
        scc.sort()
    scc_set.sort(key = lambda x : x[0])
    print(len(scc_set))
    for scc in scc_set:
        print(*scc, -1)

def input_data():
    N, M = map(int,input().split())
    adj_list, rev_adj_list = [[] for _ in range(N+1)], [[] for _ in range(N+1)]
    for _ in range(M):
        x, y = map(int,input().split())
        adj_list[x].append(y)
        rev_adj_list[y].append(x)
    return N, adj_list, rev_adj_list

N, adj_list, rev_adj_list = input_data()
fintime = dfs_list(N,adj_list)
scc_set = rev_dfs_list(N,rev_adj_list,fintime)
data_output(scc_set)

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

문제

문제

출처

ICPC

SCC 어디가 틀렸는지 모르겠습니다 ㅠㅠ

kibum1024 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말