Pagini recente » Borderou de evaluare (job #543998) | Cod sursa (job #2305995)
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
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 FileNotFoundException {
Scanner sc = new Scanner(new FileReader(INPUT_FILE_PATH));
int n = sc.nextInt();
UndirectedGraph graph = new UndirectedGraph(n);
int m = sc.nextInt();
while (m-- > 0) {
int from = sc.nextInt();
int to = sc.nextInt();
--from;
--to;
graph.addEdge(from, to);
}
PrintWriter pw = new PrintWriter(OUTPUT_FILE_PATH);
pw.println(graph.getConnectedComponents());
pw.flush();
}
static class UndirectedGraph {
private int n;
private List<List<Integer>> adjMatrix;
boolean[] visited;
UndirectedGraph(int n) {
this.n = n;
adjMatrix = new ArrayList<>();
for (int i = 0; i < n; ++i) {
adjMatrix.add(new ArrayList<>());
}
}
void addEdge(int from, int to) {
adjMatrix.get(from).add(to);
adjMatrix.get(to).add(from);
}
int getConnectedComponents() {
visited = new boolean[n];
Arrays.fill(visited, false);
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (!visited[i]) {
++cnt;
dfs(i);
}
}
return cnt;
}
private void dfs(int node) {
visited[node] = true;
adjMatrix.get(node).forEach(child -> {
if (!visited[child]) {
dfs(child);
}
});
}
}
}