Pagini recente » Cod sursa (job #2534892) | Cod sursa (job #119475) | Cod sursa (job #2530961) | Cod sursa (job #1903518) | Cod sursa (job #2675567)
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 List<List<Integer>> adjList = new ArrayList<>();
private int cntNodes;
public UndirectedGraph(int n) {
this.cntNodes = n;
for (int i = 0; i <= n; ++i) {
this.adjList.add(new ArrayList<>());
}
}
public void addEdge(int x, int y) {
this.adjList.get(x).add(y);
this.adjList.get(y).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;
for (int relatedNode : this.adjList.get(node)) {
if (!visited[relatedNode]) {
dfs(relatedNode, visited);
}
}
}
}
}