Cod sursa(job #1705747)

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

class Main {
	static List<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 ArrayList<>();
		for (int i = 0; i <= n; i++)
			graph.add(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();
	   
	}
}