글 읽기 - 반례가 뭔지 모르겠어요...

tjgy9023 2년 전 0

dfs로 풀었는데.. 왜 틀렸습니다가 뜰까요..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

	static boolean[] visited;
	static int count;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
	
		st = new StringTokenizer(br.readLine());
		
		int V = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		visited = new boolean[V];
		ArrayList<Edge>[] graph = new ArrayList[V];
		for(int i = 0; i < V; i++)
			graph[i] = new ArrayList<Edge>();
		
		
		for(int i = 0; i < M ; i++) {
			st = new StringTokenizer(br.readLine());
			int v = Integer.parseInt(st.nextToken())-1;
			int m = Integer.parseInt(st.nextToken())-1;
			
			if(v > m) { // 방향성 제거
				graph[m].add(new Edge(v));				
			}else {
				graph[v].add(new Edge(m));	
			}
		}
		
		for(int i = 0; i < V ; i++) {
			if(!visited[i]) {
				dfs(i, graph);
				count++;
			}
		}
		System.out.println(count);
		
	}
	public static void dfs(int vertax, ArrayList<Edge>[] graph) {
				
		visited[vertax] = true;
		
		for(Edge e : graph[vertax]) {
			if(!visited[e.adjVertax]) {
				dfs(e.adjVertax, graph);
			}
		}
	}
	
}

class Edge{
	int adjVertax;
	public Edge(int adjVertax) {
		this.adjVertax = adjVertax;
	}
}

djm03178 2년 전 1

방향성을 제거한 것이 잘못됐습니다.

2
3
3

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

문제

문제

출처

ICPC

반례가 뭔지 모르겠어요...

tjgy9023 2년 전 0

djm03178 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말