Cod sursa(job #1705737)

Utilizator iliaIulia Nicula ilia Data 20 mai 2016 22:40:08
Problema Parcurgere DFS - componente conexe Scor 80
Compilator java Status done
Runda Arhiva educationala Marime 1.18 kb
import java.util.*;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;

class Main {
	static Map<Integer, List<Integer>> graph;
	static boolean visited[];
	static int count = 0;
	static int N;
	
	static void dfs() {
		for (int i = 1; i < N + 1; i++) {
			if (!visited[i]) {
				count++;
				explore(i);
			}
		}
	}
	
	static void explore(int n) {
		List<Integer> successors = graph.get(n);
		visited[n] = true;
		for (Integer v : successors) {
			if (!visited[v])
				explore(v);
		}
	}
	static void init_graph(int n) {
		graph = new HashMap<Integer, List<Integer>>();
		for (int i = 1; i <= n; i++)
			graph.put(i, new ArrayList<Integer>());
	}
	
	public static void main(String[] args) throws IOException {
		Scanner input = new Scanner(new FileReader("dfs.in"));
		N = input.nextInt();
		int M = input.nextInt();
		
		visited = new boolean[N + 1];
		
		init_graph(N);
		int node1, node2;
		for (int i = 0; i < M; i++) {
			node1 = input.nextInt();
			node2 = input.nextInt();
			graph.get(node1).add(node2);
			graph.get(node2).add(node1);
		}
		input.close();
		
		dfs();
		PrintWriter output = new PrintWriter("dfs.out");
		output.println(count);
		output.close();
	   
	}
}