Mai intai trebuie sa te autentifici.
Cod sursa(job #2132195)
Utilizator | Data | 15 februarie 2018 16:01:45 | |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 75 |
Compilator | java | Status | done |
Runda | Arhiva educationala | Marime | 1.08 kb |
import java.io.*;
import java.lang.*;
import java.util.*;
public class Main {
static Vector<Integer>[] graph;
static boolean[] f;
private static void dfs(int u) {
f[u] = true;
for (int v: graph[u])
if (!f[v])
dfs(v);
}
public static void main(String[] args) throws IOException {
Scanner fi = new Scanner(new FileInputStream("dfs.in"));
PrintWriter fo = new PrintWriter("dfs.out");
int n, m, a, b;
n = fi.nextInt();
m = fi.nextInt();
f = new boolean[n + 1];
graph = new Vector[n + 1];
for (int i = 1; i <= n; ++i)
graph[i] = new Vector<>();
for (int i = 0; i < m; ++i) {
a = fi.nextInt();
b = fi.nextInt();
graph[a].add(b);
graph[b].add(a);
}
int answer = 0;
for (int i = 1; i <= n; ++i) {
if (!f[i]) {
answer += 1;
dfs(i);
}
}
fo.printf("%d\n", answer);
fi.close();
fo.close();
}
}