글 읽기 - 어디서 틀렸는지 모르겠습니다.

seccc410 6년 전 0

예제는 돌아가는데 어디가 틀렸는지 모르겠네요..

스택을 이용한 dfs 방법을 썼어요

#include<stdio.h>
#include<stack>

using namespace std;

int sumOfCon[101];
int mapOfCon[101][101];

stack<int> stk;

void dfs(int s,int N) {
	int cnt = 0;
	int top;
	int visitArr[101][2];

	for (int i = 1; i <= N; i++) {
		visitArr[i][0] = 0;
		visitArr[i][1] = 1;
	}

	stk.push(s);
	visitArr[s][0] = 1;
	while (stk.empty() != 1) {
		top = stk.top();
		stk.pop();
		for (int i = 1; i <= N; i++) {
			if (mapOfCon[top][i] == 1 && visitArr[i][0] == 0) {
				stk.push(i);
				visitArr[i][0] = 1;
				visitArr[i][1] += visitArr[top][1];
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		if(i!=s)
			sumOfCon[s] += visitArr[i][1] - 1;
	}
}

int main() {
	int N, M,s,t,ret=99999999,ans;

	scanf("%d %d", &N, &M);

	for (int i = 0; i < M; i++) {
		scanf("%d %d", &s, &t);
		mapOfCon[s][t] = 1;
		mapOfCon[t][s] = 1;
	}


	for (int i = 1; i <= N; i++) {
		dfs(i,N);
		if (ret > sumOfCon[i]) {
			ret = sumOfCon[i];
			ans = i;
		}
	}

	printf("%d", ans);
	return 0;
}

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

문제

문제

출처

ICPC

어디서 틀렸는지 모르겠습니다.

seccc410 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말