Pagini recente » Cod sursa (job #2281428) | Cod sursa (job #536421) | Cod sursa (job #1050224) | Cod sursa (job #2832584) | Cod sursa (job #1705747)
import java.util.*;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
class Main {
static List<List<Integer>> graph;
static boolean visited[];
static int count = 0;
static int N;
static void dfs() {
for (int i = 1; i < N + 1; i++) {
if (!visited[i]) {
count++;
explore(i);
}
}
}
static void explore(int n) {
List<Integer> successors = graph.get(n);
visited[n] = true;
for (Integer v : successors) {
if (!visited[v])
explore(v);
}
}
static void init_graph(int n) {
graph = new ArrayList<>();
for (int i = 0; i <= n; i++)
graph.add(new ArrayList<Integer>());
}
public static void main(String[] args) throws IOException {
Scanner input = new Scanner(new FileReader("dfs.in"));
N = input.nextInt();
int M = input.nextInt();
visited = new boolean[N + 1];
init_graph(N);
int node1, node2;
for (int i = 0; i < M; i++) {
node1 = input.nextInt();
node2 = input.nextInt();
graph.get(node1).add(node2);
graph.get(node2).add(node1);
}
input.close();
dfs();
PrintWriter output = new PrintWriter("dfs.out");
output.println(count);
output.close();
}
}