글 읽기 - 반례좀 찾아주세요.. ㅜㅜ

soloranker66 4년 전 0

반례좀 찾아주세요.. 어느부분에서 문제가 생기는걸까요

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;

struct _node {
	int indegree;
	int edge;
	int Mafia;
}v[500001];

int ans = 0;
queue<int> q;

void Cycle2(int p, int add) { // 시민이 존재하지 않는 싸이클
	if (v[p].Mafia) return;
	v[p].Mafia = 1;
	v[p].indegree--;
	ans += add;
	return Cycle2(v[p].edge, !add);
}
int Cycle(int p, int cycle) { //시민이 존재하는 싸이클
	if (v[p].Mafia==-1 && cycle) return v[p].Mafia; // 시민을 만낫다면 return
	v[p].indegree--;
	if (Cycle(v[p].edge, 1) != 1 && v[p].Mafia != -1) { // 자신이 시민이 아니고, next가 마피아가 아니면 자신은 마피아
		v[p].Mafia = 1;
		ans++;
	}
	else v[p].Mafia = -1; // 아닐경우 시민

	return v[p].Mafia;
}
int main() {
	int size;
	scanf("%d", &size);

	memset(v, 0, sizeof(v)); 

	for (int i = 1; i <= size; i++) { 
		scanf("%d", &v[i].edge);
		v[v[i].edge].indegree++;
	}
	for (int i = 1; i <= size; i++) { // indegree가 0인 노드부터 푸쉬
		if (!v[i].indegree) {
			v[i].Mafia = 1;
			q.push(i);
		}
	}
	while (!q.empty()) {
		int p = q.front();
		q.pop();
		if (v[p].Mafia == 1) ans++; // 자신이 마피아라면 ans++
		int next = v[p].edge;
		v[next].indegree--; // next indegree --
		if (v[next].indegree == 0) // next indegree가 0이라면, 푸쉬
			q.push(next);
		if (v[next].Mafia != -1) // next가 시민이 아니라면, 지금이 마피아일땐 시민, 시민일땐 마피아
			v[p].Mafia == 1 ? v[next].Mafia = -1 : v[next].Mafia = 1;
	}
	for (int i = 1; i <= size; i++) { // 시민이 존재하는 싸이클부터
		if (!v[i].indegree || v[i].Mafia != -1) continue;
		Cycle(i, 0);
	}
	for (int i = 1; i <= size; i++) { // 시민이 존재하지 않는 싸이클
		if (!v[i].indegree ) continue;
		Cycle2(i, 0);
	}
			
	printf("%d", ans);
}

soloranker66 4년 전 0

ans를 아예 빼버리고 코드를 갈아엎으니까 해결됬어요..

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

문제

문제

출처

ICPC

반례좀 찾아주세요.. ㅜㅜ

soloranker66 4년 전 0

soloranker66 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말