Pagini recente » Cod sursa (job #36628) | Cod sursa (job #2552942) | Cod sursa (job #2268906) | Cod sursa (job #2409844) | Cod sursa (job #2675569)
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.*;
public class Main {
private static final String INPUT_FILE_PATH = "dfs.in";
private static final String OUTPUT_FILE_PATH = "dfs.out";
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(new FileReader(INPUT_FILE_PATH));
PrintWriter out = new PrintWriter(OUTPUT_FILE_PATH);
int n = in.nextInt();
int m = in.nextInt();
UndirectedGraph mGraph = new UndirectedGraph(n);
while (m-- > 0) {
int source = in.nextInt();
int dest = in.nextInt();
mGraph.addEdge(source, dest);
}
int c = mGraph.countConnectedComponents();
out.print(c);
out.flush();
in.close();
out.close();
}
static class UndirectedGraph {
private Map<Integer, List<Integer>> adjList = new HashMap<>();
private int cntNodes;
public UndirectedGraph(int n) {
this.cntNodes = n;
}
public void addEdge(int x, int y) {
this.adjList.computeIfAbsent(x, k -> new ArrayList<>()).add(y);
this.adjList.computeIfAbsent(y, k -> new ArrayList<>()).add(x);
}
public int countConnectedComponents() {
boolean[] visited = new boolean[cntNodes + 1];
int cnt = 0;
for (int i = 1; i <= cntNodes; ++i) {
if (!visited[i]) {
++cnt;
dfs(i, visited);
}
}
return cnt;
}
private void dfs(int node, boolean[] visited) {
visited[node] = true;
List<Integer> relatedNodes = this.adjList.get(node);
if (relatedNodes == null) {
return;
}
for (int rNode : relatedNodes) {
if (!visited[rNode]) {
dfs(rNode, visited);
}
}
}
}
}