글 읽기 - 어떤 반례가 존재하는지 잘모르겠습니다

tlfla01 5년 전 0

dfs를 이용해서 사이클을 찾고 문제에서 주어진 조건에 맞게 값을 정렬해서 출력시켰는데 9%까지 가다가 틀렸다고 나오네요. 어떤 반례가 있을까요?

#include <cstdio>
#include <vector>
#include <cstring>

#define SIZE 10001

using namespace std;

int k, v;
vector<vector<int> > adj;
bool visited[SIZE]; //dfs 경로용
int checked[SIZE]; //사이클 표시용
bool num_checked[SIZE]; //정렬시 이용
int cnt = 0;
int group_num = 1; //사이클의 그룹들을 같은 숫자로 표시 -> checked 배열에 이용

void dfs(int now, int start) {	
	if (now == start && visited[now]==true) {
		cnt++;
		for (int i = 1; i <= k; i++) 
			if (visited[i]) 
				checked[i] = group_num;
					
		group_num++;
	}
	for (int i = 0; i < adj[now].size(); i++) {
		if (!visited[adj[now][i]]) {
			visited[adj[now][i]] = true;
			dfs(adj[now][i],start);
		}
	}
}
int main() {	
	scanf("%d %d", &k, &v);
	adj.resize(k + 1);
	
	for (int i = 0; i < v; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		adj[x].push_back(y);
	}
	
	memset(checked, 0, sizeof(checked));
	for (int i = 1; i <= k; i++) {		
		if (checked[i]==0) {
			memset(visited, false, sizeof(visited));
			dfs(i, i);
		}
	}//dfs

	for (int i = 1; i <= k; i++) {
		if (checked[i]==0) {
			checked[i] = group_num;
			group_num++;
			cnt++;
		}			
	}//사이클이 이루어지지 않은 정점들을 표시

	printf("%d\n", cnt);
	
	memset(num_checked, false, sizeof(num_checked));
	for (int i = 1; i <= k; i++) {
		int num_check = checked[i];
		bool print_minus = false;
		for (int j = 1; j <= k; j++) {
			if (num_check == checked[j]&&!num_checked[j]) {
				printf("%d ", j);
				print_minus = true;
				num_checked[j] = true;
			}
		}
		if(print_minus)
			printf("-1\n");
	}//정렬 및 출력
}

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

문제

문제

출처

ICPC

어떤 반례가 존재하는지 잘모르겠습니다

tlfla01 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말