글 읽기 - 오답 질문입니다 ㅠㅠ

fisache 7년 전 0

알고리즘 문제 해결 전략보면서 역방향 간선을 이용해 사이클 찾는 걸 구현했는데 오답이 나와서요 ㅠㅠ

본인 지목의 경우와 역방향 간선이 존재하면 사이클을 이루게 되니까 vector에 저장했습니다.

어디서 잘못된건가요?ㅠㅠㅠ

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

vector<int> adj;

vector<int> discovered, finished;
vector<int> cycle;

int counter;

void dfsAll();
void dfs(int here);
int main()
{
    int testCase;
    scanf("%d", &testCase);
    while(testCase--) {
        int n;
        scanf("%d", &n);
        counter = 0;
        adj = vector<int>(n+1);
        discovered = vector<int>(n+1, -1);
        cycle = vector<int>(n+1, 0);
        finished = vector<int>(n+1, 0);
        for(int i=1; i<=n; i++) {
            scanf("%d", &adj[i]);
        }
 
        dfsAll();
        int ret = 0;
        for(int i=1; i<cycle.size(); i++) {
            if(cycle[i] == 0) ret++;
        }
        printf("%d\n", ret);
    }
    return 0;
}

void dfsAll()
{
    for(int i=1; i<adj.size(); i++) {
        if(discovered[i] == -1) {
            dfs(i);
        }
    }
}

void dfs(int here)
{
    discovered[here] = counter++;
 
    int there = adj[here];
    // 본인 지목
    if(here == there) {
        // 본인 지목의 경우 호출했던 정점은 사이클에 포함되지 않는다.
        cycle[here] = 2;
    }
    // 방문 안함
    else if(discovered[there] == -1) {
        dfs(there);
        if(cycle[there] == 1) cycle[here] = 1;
    }
    // 역방향
    else if(discovered[here] > discovered[there] &&
           finished[there] == 0) {
        cycle[here] = 1;
    }

    finished[here] = 1;
}

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

문제

문제

출처

ICPC

오답 질문입니다 ㅠㅠ

fisache 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말