Cod sursa(job #1356964)

Utilizator vlad.maneaVlad Manea vlad.manea Data 23 februarie 2015 17:56:29
Problema Parcurgere DFS - componente conexe Scor 55
Compilator java Status done
Runda Arhiva educationala Marime 2.21 kb
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Graph {
	private final List<List<Integer>> adjacencyLists;
	private List<Boolean> visited;
	
	Graph(List<List<Integer>> adjacencyLists) {
		this.adjacencyLists = adjacencyLists;
	}
	
	int countConnectedComponents() {
		int countComponents = 0;		
		this.visited = new ArrayList<Boolean>(adjacencyLists.size());
		
		for (int i = 0; i < this.adjacencyLists.size(); ++i) {
			this.visited.add(false);
		}

		for (int i = 0; i < adjacencyLists.size(); ++i) {
			if (this.visited.get(i)) {
				continue;
			}
			
			bfsComponent(i);
			++countComponents;
		}
		
		return countComponents;
	}
	
	void bfsComponent(int node) {
		this.visited.set(node, true);
		List<Integer> adjacencyList = this.adjacencyLists.get(node);
		
		for (int j = 0; j < adjacencyList.size(); ++j) {
			int sibling = adjacencyList.get(j);
			
			if (this.visited.get(sibling)) {
				continue;
			}
			
			bfsComponent(sibling);
		}
	}
}

public class Main {
	public static void main(String[] args) throws IOException {
		InputStream inputStream = new FileInputStream("dfs.in");
		Scanner scanner = new Scanner(inputStream);
		OutputStream outputStream = new FileOutputStream("dfs.out");
		Writer printer = new PrintWriter(outputStream);
		
		int N = scanner.nextInt();
		int M = scanner.nextInt();
		
		List<List<Integer>> adjacencyLists = new ArrayList<List<Integer>>();
		
		for (int i = 0; i < N; ++i) {
			adjacencyLists.add(new ArrayList<Integer>());
		}
		
		for (int j = 0; j < M; ++j) {
			int x = scanner.nextInt() - 1;
			int y = scanner.nextInt() - 1;
			
			adjacencyLists.get(x).add(y);
			adjacencyLists.get(y).add(x);
		}
		
		Graph graph = new Graph(adjacencyLists);
		int countConnectedComponents = graph.countConnectedComponents();
		
		printer.write(String.valueOf(countConnectedComponents));
		printer.flush();
		
		scanner.close();
		inputStream.close();
		outputStream.close();
		printer.close();
	}
}