글 읽기 - dfs인데 틀렸습니다

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

dfs인데 틀렸습니다

9466번 - 텀 프로젝트

boringcoding 1년 전 0

케이스마다 초기화 하고, cc에 사이클인 노드수, isSolo에 혼자인 노드를 구하고 전체에서 뺐는데 안되네요

dfs에서는 일단 엣지를 탈때마다 cc++를 하고 사이클이 안되면, 탈출하면서 cc--를 합니다

반례가 있을까요

#include<iostream>
using namespace std;
int graph[100001];
int visit[100001];
int n, isSolo, isCycle, flag, cc;
void dfs(int v) {
	visit[v] = 1;
	cc++;
	if (graph[v] == flag) {
		isCycle = 1;
		return;
	}
	if (visit[graph[v]] == 0)
		dfs(graph[v]);
	if (isCycle)
		return;
	cc--;
	visit[graph[v]] = 0;
}
void dfs() {
	int a;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		visit[i] = 0;
		cin >> graph[i];
	}
	
	isSolo = 0;
	isCycle = 0;
	cc = 0;
	for (int i = 1; i <= n; i++) {
		if (i == graph[i]) {
			visit[i] = 1;
			isSolo++;
		}
		else if(cc == 0) {
			flag = i;
			dfs(i);
		}
	}
	cout << n-cc-isSolo << "\n";
}
int main() {
	int tc;
	cin >> tc;
	for (int i = 0; i < tc; i++) {
		dfs();
	}
	return 0;
}