글 읽기 - 반례가 있다면 알려주세요

hds1630 6년 전 0

혼자있는 정점을 고려하지 않았다가 수정해서 채점해도 틀리다고 나오는데 또 다른 반례가 있는건지 잘 모르겠습니다.. 문제점 좀 알려주세요.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static int n, m;
	static int[][] arr;
	static boolean[] visited;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] line = br.readLine().split(" ");
		n = Integer.parseInt(line[0]);
		m = Integer.parseInt(line[1]);

		arr = new int[n + 1][n + 1];
		visited = new boolean[n + 1];

		for (int i = 0; i < m; i++) {
			String[] row = br.readLine().split(" ");
			int u = Integer.parseInt(row[0]);
			int v = Integer.parseInt(row[1]);
			arr[u][v] = 1;
		}

		int res = 0;
		for (int i = 1; i <= n; i++) {
			if (!visited[i]) {
				res++;
				dfs(i);
			}
		}
		System.out.println(res);
	}

	static void dfs(int here) {
		visited[here] = true;
		int cnt = 0;

		for (int there = 1; there <= n; there++) {
			if (arr[here][there] == 1)
				cnt++;
		}

        // 혼자 있는 정점 카운트
		if (cnt == 0)
			return;
        // 간선이 있는 경우 dfs
		else {
			for (int there = 1; there <= n; there++) {
				if (arr[here][there] == 1 && !visited[there])
					dfs(there);
			}
		}
	}
}

djm03178 6년 전 1

방향이 없는 그래프라는 말은 간선은 양방향이라는 말과 같습니다.

2 1

정답은 1입니다.

hds1630 6년 전 0

감사합니다!! 질문사항에 있는 문제만 고치고 어떻게 보면 가장 기본적인걸 생각하지 못했어요..

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

문제

문제

출처

ICPC

반례가 있다면 알려주세요

hds1630 6년 전 0

djm03178 6년 전 1

hds1630 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말