Pagini recente » Cod sursa (job #1997911) | Cod sursa (job #3266150)
import java.io.*;
import java.util.*;
public class Main {
public static class UndirectedGraph {
private List<Integer>[] adj;
public UndirectedGraph(int nodes) {
adj = (List<Integer>[]) new List[nodes + 1];
}
public void addEdge(int u, int v) {
if (adj[u] == null) {
adj[u] = new LinkedList<>();
}
adj[u].add(v);
if (adj[v] == null) {
adj[v] = new LinkedList<>();
}
adj[v].add(u);
}
}
private static void dfsVisit(UndirectedGraph g, int u, boolean[] hasVisited) {
hasVisited[u] = true;
List<Integer> neighbors = g.adj[u];
if (neighbors != null) {
for (int v : neighbors) {
if (!hasVisited[v]) {
dfsVisit(g, v, hasVisited);
}
}
}
}
public static int dfs(UndirectedGraph g) {
boolean[] hasVisited = new boolean[g.adj.length];
Arrays.fill(hasVisited, false);
Set<Integer> visited = new HashSet<>();
int connectedComp = 0;
for (int u = 1; u < g.adj.length; u++) {
if (!hasVisited[u]) {
dfsVisit(g, u, hasVisited);
connectedComp++;
}
}
return connectedComp;
}
public static void main(String[] args) throws IOException {
// long start = System.currentTimeMillis();
BufferedReader reader = new BufferedReader(new FileReader("dfs.in"));
PrintWriter out = new PrintWriter(new OutputStreamWriter(new FileOutputStream("dfs.out"), "UTF-8"), true);
String line = reader.readLine();
String[] parts = line.split(" ");
int N = Integer.parseInt(parts[0]);
int M = Integer.parseInt(parts[1]);
UndirectedGraph g = new UndirectedGraph(N);
for (int i = 0; i < M; i++) {
line = reader.readLine();
parts = line.split(" ");
g.addEdge(Integer.parseInt(parts[0]), Integer.parseInt(parts[1]));
}
out.println(dfs(g));
out.close();
// long now = System.currentTimeMillis();
// System.out.println((now - start));
// UndirectedGraph g = new UndirectedGraph(6);
// g.addEdge(1, 2);
// g.addEdge(1, 4);
// g.addEdge(3, 5);
// System.out.println(dfs(g));
}
}