Pagini recente » Cod sursa (job #1740433) | Cod sursa (job #1744906) | Cod sursa (job #529003) | Cod sursa (job #2912753) | Cod sursa (job #3353024)
import java.util.*;
import java.io.*; // Necesar pentru File si PrintWriter
public class Main {
static int n, m;
static ArrayList<Integer>[] graph;
static int[] vizitat;
static int componente = 0;
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(new File("dfs.in"));
if (!sc.hasNextInt()) return;
n = sc.nextInt();
m = sc.nextInt();
graph = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 1; i <= m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
graph[a].add(b);
graph[b].add(a);
}
vizitat = new int[n + 1];
for (int i = 1; i <= n; i++) {
if (vizitat[i] == 0) {
dfsIterativ(i);
componente++;
}
}
PrintWriter pw = new PrintWriter(new File("dfs.out"));
pw.println(componente);
pw.close();
sc.close();
}
private static void dfsIterativ(int startNode) {
ArrayDeque<Integer> stack = new ArrayDeque<>();
stack.push(startNode);
vizitat[startNode] = 1;
while (!stack.isEmpty()) {
int nod = stack.pop();
for (int vecin : graph[nod]) {
if (vizitat[vecin] == 0) {
vizitat[vecin] = 1;
stack.push(vecin);
}
}
}
}
}