Pagini recente » Cod sursa (job #2601894) | Cod sursa (job #595158) | Cod sursa (job #1183212) | Cod sursa (job #1280256) | Cod sursa (job #3298715)
import java.io.File;
import java.io.PrintWriter;
import java.util.*;
public class Main {
static boolean[] visited;
static ArrayList<Integer>[] adj;
static void dfs(int start) {
Stack<Integer> stack = new Stack<>();
stack.push(start);
visited[start] = true;
while (!stack.isEmpty()) {
int node = stack.pop();
for (int neigh : adj[node]) {
if (!visited[neigh]) {
visited[neigh] = true;
stack.push(neigh);
}
}
}
}
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(new File("dfs.in"));
PrintWriter out = new PrintWriter("dfs.out");
int n = sc.nextInt();
int m = sc.nextInt();
adj = new ArrayList[n + 1];
visited = new boolean[n + 1];
for (int i = 1; i <= n; i++) {
adj[i] = new ArrayList<>();
}
for (int i = 0; i < m; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
adj[u].add(v);
adj[v].add(u);
}
int cc = 0;
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
cc++;
dfs(i); // DFS, dar iterativ!
}
}
out.println(cc);
out.close();
}
}