Pagini recente » Cod sursa (job #2598357) | Cod sursa (job #2453699) | Cod sursa (job #1555661) | Cod sursa (job #428375) | Cod sursa (job #1689584)
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();
}
}