Pagini recente » Istoria paginii runda/oni/clasament | Borderou de evaluare (job #1851504) | Cod sursa (job #830204) | Cod sursa (job #2696394) | Cod sursa (job #2606359)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
Graph graph = new Graph("dfs.in");
FileWriter fileWriter = new FileWriter("dfs.out");
PrintWriter printWriter = new PrintWriter(fileWriter);
printWriter.print(graph.num_conn_comp());
printWriter.close();
fileWriter.close();
}
}
class Graph {
public Graph(final String filename) throws FileNotFoundException {
File file = new File(filename);
Scanner scanner = new Scanner(file);
int n, m;
n = scanner.nextInt();
m = scanner.nextInt();
adj_list = new ArrayList<>();
for (int i = 0; i <= n; i++) {
adj_list.add(new ArrayList<>());
}
int f, g, h;
for (int i = 0; i < m; i++) {
f = scanner.nextInt();
g = scanner.nextInt();
adj_list.get(f).add(g);
adj_list.get(g).add(f);
}
scanner.close();
}
public int num_conn_comp() {
ArrayList<Boolean> seen = new ArrayList<>(Collections.nCopies(adj_list.size(), Boolean.FALSE));
int k = 0;
for (int i = 1; i < adj_list.size(); i++) {
if (seen.get(i) == Boolean.FALSE) {
k++;
dfs(i, seen);
}
}
return k;
}
private void dfs(int i, ArrayList<Boolean> seen) {
if (seen.get(i) == Boolean.TRUE) return;
seen.set(i, Boolean.TRUE);
for (int e : adj_list.get(i))
dfs(e, seen);
}
private ArrayList<ArrayList<Integer>> adj_list;
};