글 읽기 - [9466 텀프로젝트] int 배열을 사용했습니다.. 오답이유 부탁드립니다..

ryujh111 3년 전 0

너무 답답하네요..

감사합니다.

#include <stdio.h>
#include <cstring>
#include <vector>
using namespace std;

int visited[100001];
int graph[100001];

void DFS(int _start, int _root) {
   visited[_start] = 1;
   if (visited[graph[_start]] == -1) {
      visited[_start] = -1;
      return;
   }
   if (visited[graph[_start]] == 1) {
      //a cycle was made
      int idx = _root;
      while (idx != graph[_start]) {
         visited[idx] = -1;
         idx = graph[idx];
      }
      return;
   }
   if (visited[graph[_start]] == 0)
      DFS(graph[_start], _root);
}

int main() {
   int TC, num_r, v;
   scanf("%d", &TC);
   for (int i = 0; i < TC; ++i) {
      memset(visited, 0, sizeof(visited));
      memset(graph, 0, sizeof(graph));
      int Count = 0;
      scanf("%d", &num_r);
      for (int j = 1; j < num_r + 1; ++j) {
         scanf("%d", &v);
         graph[j] = v;
      }
      for (int j = 1; j < num_r + 1; ++j) {
         if (visited[j] == 0) {
            DFS(j, j);
         }
      }
      for (int j = 1; j < num_r + 1; ++j) {
         if (visited[j] == -1) {
            ++Count;
         }
      }

      printf("%d\n", Count);
   }
    return 0;
}

seokjeongeum 3년 전 0

코드는 이렇게 써주세요

#include <stdio.h>
#include <cstring>
#include <vector>
using namespace std;

int visited[100001];
int graph[100001];

void DFS(int _start, int _root) {
   visited[_start] = 1;
   if (visited[graph[_start]] == -1) {
      visited[_start] = -1;
      return;
   }
   if (visited[graph[_start]] == 1) {
      //a cycle was made
      int idx = _root;
      while (idx != graph[_start]) {
         visited[idx] = -1;
         idx = graph[idx];
      }
      return;
   }
   if (visited[graph[_start]] == 0)
      DFS(graph[_start], _root);
}

int main() {
   int TC, num_r, v;
   scanf("%d", &TC);
   for (int i = 0; i < TC; ++i) {
      memset(visited, 0, sizeof(visited));
      memset(graph, 0, sizeof(graph));
      int Count = 0;
      scanf("%d", &num_r);
      for (int j = 1; j < num_r + 1; ++j) {
         scanf("%d", &v);
         graph[j] = v;
      }
      for (int j = 1; j < num_r + 1; ++j) {
         if (visited[j] == 0) {
            DFS(j, j);
         }
      }
      for (int j = 1; j < num_r + 1; ++j) {
         if (visited[j] == -1) {
            ++Count;
         }
      }

      printf("%d\n", Count);
   }
    return 0;
}

ryujh111 3년 전 0

좋은 가르침 감사합니다..

doxxx93 1년 전 0

답변 코드가 질문코드랑 같은데 일부러 바꾸신거려나요

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

문제

문제

출처

ICPC

[9466 텀프로젝트] int 배열을 사용했습니다.. 오답이유 부탁드립니다..

ryujh111 3년 전 0

seokjeongeum 3년 전 0

ryujh111 3년 전 0

doxxx93 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말