글 읽기 - 1%채점 중 후에 틀렸다고 뜨네요. 뭐가 잘못된 것일까요 ㅠㅠ

alpa1072 3년 전 0

예제 잘 나오는데요..ㅜㅠㅜ 예외케이스가 있을까요?

#include<cstdio>
using namespace std;

int cnt,origin,temp;
int d[100002];
bool visited[100002];

void dfs(int i) {
    if(origin == i) {
        cnt += temp; //같은 집합에 들어 있는 수 만큼 더함.
        return;
    }
    if(!visited[i]) {
        visited[i] = true; //한 번 방문한 것은 이미 결정이 난 것이므로 재방문 방지
        temp ++;
        dfs(d[i]);
    }
    else
        return;
}

int main(void) {
    int T;
    scanf("%d",&T);
    for(int t=0;t<T;t++) {
        cnt = 0;
        int total;
        scanf("%d",&total);
        for(int i=1;i<=total;i++) {
        scanf("%d",&d[i]);
        visited[i] = false;
        if(i==d[i]) {
            cnt++; //사이클인 것은 미리 개수 추가
            visited[i] = true; //자신이 cycle인 것은 미리 체크(후에 방문 안 함)
        }
    }

    for(int i=1;i<=total;i++) {
        if(!visited[i]) {
            visited[i] = true;
            origin = i; //사이클이 생성된다면 초기 값
            temp = 1;
            dfs(d[i]);
        }
    }
    printf("%d\n",total-cnt);
    }
    return 0;
}

zasxer 3년 전 0

2 3 2

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

문제

문제

출처

ICPC

1%채점 중 후에 틀렸다고 뜨네요. 뭐가 잘못된 것일까요 ㅠㅠ

alpa1072 3년 전 0

zasxer 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말