글 읽기 - [C언어]고수님들 제발도와주세요.. dfs로 짰는데..

jjy1715 6년 전 0

뭐가 문제일까요... 답이 자꾸 다르게 나오네요

#include<stdio.h>
#include<stdlib.h> // qsort
#include<string.h> // memset

int arr[1000] = {0,};
int temp[1000] = {0,};
int result[1001][1001] = {0,};
int v[1001] = {0,};
int count = 0;

//오름차순 정렬
int compare(const void *first, const void *second) {
	if (*(int*)first > *(int*)second) return 1;
	else if (*(int*)first < *(int*)second) return -1;
	else return 0;
}

void dfs(int n, int s, int sw) {
	
	if (v[s] == 1) return;

	v[s] = 1;

	for (int i = 1; i <= n; i++) {
		if (result[s][i] == 1 && v[s] != 1) {
			dfs(n, i, sw);
		}
	}

	if (sw == 1) return;
	sw = 1;
	count++;
}


int main(void) {

	int n;
	scanf("%d", &n);

	for (int i = 1; i <= n; i++) {

		memset(arr, 0, sizeof(arr));
		memset(temp, 0, sizeof(temp));
		memset(result, 0, sizeof(result));
		memset(v, 0, sizeof(v));
		count = 0;

		int num;
		scanf("%d", &num);

		for (int i = 0; i < num; i++) {
			scanf("%d", &arr[i]);
			temp[i] = arr[i];
		}

		qsort(temp, num, sizeof(temp[0]), compare);

		int start;
		int finish;
		for (int i = 0; i < num; i++) {
			start = temp[i];
			finish = arr[i];
			result[start][finish] = 1;
		}

		for (int i = 1; i <= num; i++) {
			dfs(num,i,0);
		}

		printf("%d\n", count);

	}

	return 0;
}

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

문제

문제

출처

ICPC

[C언어]고수님들 제발도와주세요.. dfs로 짰는데..

jjy1715 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말