Pagini recente » Cod sursa (job #752406) | Cod sursa (job #1435153) | Cod sursa (job #381808) | Cod sursa (job #543958) | Cod sursa (job #2090164)
import java.io.*;
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);
}
out.print(mGraph.countConnectedComponents());
out.flush();
in.close();
out.close();
}
static class UndirectedGraph {
private List<List<Integer>> adjList;
private int cntNodes;
private boolean[] isReached;
public UndirectedGraph(int n) {
this.cntNodes = n;
this.adjList = new ArrayList<>();
for (int i = 0; i <= n; ++i) {
this.adjList.add(new ArrayList<Integer>());
}
this.isReached = new boolean[n + 1];
Arrays.fill(isReached, false);
}
public void addEdge(int source, int dest) {
this.adjList.get(source).add(dest);
this.adjList.get(dest).add(source);
}
public int countConnectedComponents() {
int cnt = 0;
Arrays.fill(isReached, false);
for (int i = 1; i <= this.cntNodes; ++i) {
if (!isReached[i]) {
dfs(i);
++cnt;
}
}
return cnt;
}
private void dfs(int i) {
this.isReached[i] = true;
List<Integer> neighbList = this.adjList.get(i);
for (int neighbor : neighbList) {
if (!isReached[neighbor]) {
dfs(neighbor);
}
}
}
}
}