Cod sursa(job #1689584)

Utilizator vladmatei0Vlad Matei vladmatei0 Data 14 aprilie 2016 13:07:30
Problema Parcurgere DFS - componente conexe Scor 60
Compilator java Status done
Runda Arhiva educationala Marime 2.69 kb
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.Writer;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;

class Graph<T> {
	class Edge {
		T node1;
		T node2;

		Edge() {

		}

		Edge(T node1, T node2) {
			this.node1 = node1;
			this.node2 = node2;
		}
	}

	public Set<Edge> edges = new HashSet<Edge>();
	public Set<T> vertexList = new HashSet<T>();

}

class DF<T> {
	Graph<T> input;
	HashMap<T, Set<T>> graph = new HashMap<T, Set<T>>();
	HashSet<T> seen = new HashSet<T>();

	DF(Graph<T> graph) {
		this.input = graph;
		convertGraph();
	}

	private void convertGraph() {
		for (Graph<T>.Edge edge : input.edges) {
			if (!graph.containsKey(edge.node1)) {
				graph.put(edge.node1, new HashSet<T>());
			}
			graph.get(edge.node1).add(edge.node2);
		}
	}

	// private void df(T node) {
	// seen.add(node);
	// if (!graph.containsKey(node)) {
	// return;
	// }
	//
	// for (T neighbour : graph.get(node)) {
	// if (!seen.contains(neighbour)) {
	// df(neighbour);
	// }
	// }
	// }

	private void df(T node) {
		Stack<T> stack = new Stack<T>();
		stack.add(node);

		while (!stack.empty()) {
			T top = stack.pop();
			seen.add(top);
			if (!graph.containsKey(top)) {
				continue;
			}
			for(T neighbour : graph.get(top)){
				if(!seen.contains(neighbour)){
					stack.push(neighbour);
				}
			}
		}
	}

	int dfs() {
		int result = 0;

		for (T node : input.vertexList) {
			if (!seen.contains(node)) {
				df(node);
				result++;
			}
		}
		return result;
	}
}

public class Main {
	private final String input;
	private final String output;
	private int n, m;
	private Set<Graph<Integer>.Edge> edges = new HashSet<Graph<Integer>.Edge>();
	private Graph<Integer> graph = new Graph<Integer>();

	Main(String input, String output) {
		this.input = input;
		this.output = output;
	}

	private void read() throws IOException {
		Scanner scanner = new Scanner(new FileReader(input));
		n = scanner.nextInt();
		m = scanner.nextInt();
		for (int i = 0; i < m; i++) {
			int node1 = scanner.nextInt();
			int node2 = scanner.nextInt();
			edges.add(graph.new Edge(node1, node2));
			edges.add(graph.new Edge(node2, node1));
		}
		graph.edges = edges;
		for (int i = 1; i <= n; i++) {
			graph.vertexList.add(i);
		}
		scanner.close();
	}

	private void write(int i) throws IOException {
		Writer writer = new FileWriter(output);
		writer.write(Integer.toString(i));
		writer.flush();
		writer.close();
	}

	void solve() throws IOException {
		read();
		DF<Integer> df = new DF(graph);
		write(df.dfs());
	}

	public static void main(String[] args) throws IOException {
		Main main = new Main("dfs.in", "dfs.out");
		main.solve();
	}

}