Pagini recente » Cod sursa (job #2563115) | Cod sursa (job #1297000) | Cod sursa (job #2630854) | Cod sursa (job #610128) | Cod sursa (job #3122951)
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(new File("dfs.in"));
FileWriter fw = new FileWriter("dfs.out");
int n;
long m;
ArrayList<Integer>[] adj = new ArrayList[(int) 1e5 + 1];
n = sc.nextInt();
m = sc.nextLong();
for (int i = 1; i <= n; i++) {
adj[i] = new ArrayList<>();
}
for (int i = 1; i <= m; i++) {
int x = sc.nextInt();
int y = sc.nextInt();
adj[x].add(y);
adj[y].add(x);
}
// Rezolva folosind Stack, iterativ
Stack<Integer> stack = new Stack<>();
boolean[] visited = new boolean[n + 1];
int nrCC = 0;
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
nrCC++;
stack.push(i);
visited[i] = true;
while (!stack.isEmpty()) {
int node = stack.pop();
for (int neigh : adj[node]) {
if (!visited[neigh]) {
stack.push(neigh);
visited[neigh] = true;
}
}
}
}
}
fw.write(String.valueOf(nrCC));
sc.close();
fw.close();
}
}