Pagini recente » Cod sursa (job #2186731) | Cod sursa (job #2102316) | Cod sursa (job #1661218) | Cod sursa (job #107947) | Cod sursa (job #3122948)
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
public class ComponenteConexe {
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[] viz = new int[n + 1];
int nrCC = 0;
for (int i = 1; i <= n; i++) {
if (viz[i] == 0) {
nrCC++;
dfs(i, adj, viz);
}
}
fw.write(String.valueOf(nrCC));
sc.close();
fw.close();
}
private static void dfs(int i, ArrayList<Integer>[] adj, int[] viz) {
viz[i] = 1;
for (int j = 0; j < adj[i].size(); j++) {
if (viz[adj[i].get(j)] == 0) {
dfs(adj[i].get(j), adj, viz);
}
}
}
}