글 읽기 - 틀린 부분 알려주시면 감사하겠습니다.

(追記) (追記ここまで)

틀린 부분 알려주시면 감사하겠습니다.

9466번 - 텀 프로젝트

yoyo5809 7달 전 0

골자는 주어진 그래프를 1번 노드부터 n번 노드까지 순차적으로 탐색해서 방문한 노드에 대해서 방문확인을 하고, 루프를 찾으면 루프인 노드들만 따로 저장을 해놔서 같은 루프를 두 번 세는 일을 방지하려고 했습니다.

예상하기로는 루프에 중간에 끼어드는 노드가 있을 경우 문제가 생기는 것 같은데 반례를 아무리 생각해봐도 생각나는 바가 없습니다.

논리의 틀린 점이나 반례를 주시면 감사하겠습니다.

#include <bits/stdc++.h>
using namespace std;
int f(vector<int> &v, vector<int> &visit, vector<int> &loop, int i){
 int x = v[i];
 while(!visit[i]){
 visit[i] = 1;
 i = x;
 x = v[i];
 }
 int cnt = 0;
 while(!loop[i]){
 loop[i] = 1;
 ++cnt;
 i = x;
 x = v[i];
 }
 return cnt;
}
int main()
{
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 int t;
 cin >> t;
 while(t--){
 int n;
 cin >> n;
 vector<int> v(n + 1);
 for(int i = 1; i <= n; ++i) cin >> v[i];
 vector<int> visit(n + 1);
 vector<int> loop(n + 1);
 int cnt = 0;
 for(int i = 1; i <= n; ++i){
 if(visit[i] || visit[v[i]]) continue;
 cnt += f(v, visit, loop, i);
 }
 cout << n - cnt << '\n';
 }
}

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC