Pagini recente » Cod sursa (job #2010789) | Cod sursa (job #1984489) | Cod sursa (job #1999543) | Cod sursa (job #885238) | Cod sursa (job #3122956)
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);
}
int nrCC = 0;
// Rezolva folosind Stack, iterativ
// Stack<Integer> stack = new Stack<>();
// boolean[] visited = new boolean[n + 1];
//
// 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;
// }
// }
// }
// }
// }
// Rezolva folosind recursivitate
boolean[] visited = new boolean[n + 1];
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
nrCC++;
dfs(i, adj, visited);
}
}
fw.write(String.valueOf(nrCC));
sc.close();
fw.close();
}
private static void dfs(int i, ArrayList<Integer>[] adj, boolean[] visited) {
visited[i] = true;
for (int neigh : adj[i]) {
if (!visited[neigh]) {
dfs(neigh, adj, visited);
}
}
}
}