Cod sursa(job #1239743)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 9 octombrie 2014 18:33:15
Problema Parcurgere DFS - componente conexe Scor 55
Compilator java Status done
Runda Arhiva educationala Marime 1.16 kb
import java.io.*;
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;

public class Main {
	private static List<List<Integer>> G;
	private static int V;
	private static boolean[] Visited;
	
	private static void DFS(final int x) {
		Visited[x] = true;
		for (int y: G.get(x))
			if (!Visited[y])
				DFS(y);
	}
	
	private static void addEdge(final int x, final int y) {
		G.get(x).add(y);
		G.get(y).add(x);
	}
	
	public static void main(String[] args) throws IOException {
		Scanner reader = new Scanner(new FileInputStream("dfs.in"));
		V = reader.nextInt();
		G = new ArrayList<List<Integer>>(V);
		for (int x = 0; x < V; ++x)
			G.add(new ArrayList<Integer>());
		int edgeCount = reader.nextInt();
		for (; edgeCount > 0; --edgeCount) {
			int x = reader.nextInt() - 1;
			int y = reader.nextInt() - 1;
			addEdge(x, y);
		}
		Visited = new boolean[V];
		reader.close();
		
		int componentCount = 0;
		for (int x = 0; x < V; ++x) {
			if (!Visited[x]) {
				++componentCount;
				DFS(x);
			}
		}
		
		PrintWriter writer = new PrintWriter("dfs.out");
		writer.write(componentCount + "\n");
		writer.close();
	}
}