Pagini recente » Cod sursa (job #2200329) | Cod sursa (job #205101) | Cod sursa (job #351668) | Cod sursa (job #3337100) | Cod sursa (job #3353025)
import java.util.*;
import java.io.*;
public class Main {
static int n, m;
static ArrayList<Integer>[] graph;
static int[] vizitat;
// Clasa pentru citire rapida
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader(String fileName) throws FileNotFoundException {
br = new BufferedReader(new FileReader(fileName));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
}
public static void main(String[] args) throws IOException {
FastReader fr = new FastReader("dfs.in");
n = fr.nextInt();
m = fr.nextInt();
graph = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 0; i < m; i++) {
int u = fr.nextInt();
int v = fr.nextInt();
graph[u].add(v);
graph[v].add(u);
}
vizitat = new int[n + 1];
int componente = 0;
for (int i = 1; i <= n; i++) {
if (vizitat[i] == 0) {
componente++;
dfsIterativ(i);
}
}
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("dfs.out")));
pw.println(componente);
pw.close();
}
private static void dfsIterativ(int startNode) {
ArrayDeque<Integer> stack = new ArrayDeque<>();
stack.push(startNode);
vizitat[startNode] = 1;
while (!stack.isEmpty()) {
int node = stack.pop();
for (int neigh : graph[node]) {
if (vizitat[neigh] == 0) {
vizitat[neigh] = 1;
stack.push(neigh);
}
}
}
}
}