Pagini recente » Cod sursa (job #798956) | Cod sursa (job #626552) | Cod sursa (job #802322) | Cod sursa (job #2407324) | Cod sursa (job #3032870)
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.util.*;
public class Main {
public static void main(String[] args) throws FileNotFoundException {
File in = new File("dfs.in");
Scanner sc = new Scanner(in);
int n = sc.nextInt();
int m = sc.nextInt();
Graf graf = new Graf(n);
for (int i = 0; i < m; i++) {
int x = sc.nextInt();
int y = sc.nextInt();
graf.adaugareMuchie(x,y);
}
//in mom acesta avem graful facut
int nrConexe = 0;
for (int i = 1; i <= n; i++) {
if (graf.viz[i]) continue;
graf.dfs(i);
nrConexe++;
}
File out = new File("dfs.out");
PrintStream p = new PrintStream(out);
p.println(nrConexe);
// Daca nu inchidem fisierul, nu se salveaza!!
p.close();
}
}
class Graf {
// numarul de varfuri
public final int N;
// vector de vizitare
final boolean[] viz;
// listele de adiacenta
public final List<List<Integer>> adjLists;
public Graf(int n) {
this.N = n;
viz = new boolean[n + 1];
// VARIANTA CU LISTE ADIACENTA
// n + 1 pt ca vom incepe numerotarea de la 1 in loc de 0 (indexul 0 va fi ignorat)
adjLists = new ArrayList<>(n + 1);
adjLists.add(null); // valoarea de la index 0 este null (nu e folosita)
for (int i = 1; i <= n; i++) {
adjLists.add(new ArrayList<>());
}
}
// pentru graf orientat
public void adaugareArc(int sursa, int destinatie) {
List<Integer> list = adjLists.get(sursa);
list.add(destinatie);
}
// pentru graf neorientat
public void adaugareMuchie(int a, int b) {
adaugareArc(a, b);
adaugareArc(b, a);
}
public boolean existaArc(int sursa, int destinatie) {
// varianta cu matrice
//return adjMatrix[sursa][destinatie];
// varianta cu liste de adiacenta
List<Integer> list = adjLists.get(sursa);
return list.contains(destinatie);
}
// complexitate O(N + M)
// functia se apeleaza de n ori
// interior-ul forului de m ori
public void dfs(int start) {
viz[start] = true;
List<Integer> list = adjLists.get(start);
for (int urm : list) {
if (viz[urm]) continue;
dfs(urm);
}
// pentru matrice
// for (int j = 1; j <= N; j++) {
// if (adjMatrix[start][j] == false) continue;
// if (viz[j]) continue;
// if (dfsHelper(j, destinatie)) return true;
// }
}
// tot O(N + M)
public boolean bfs(int start, int destinatie) {
for (int i = 1; i <= N; i++) viz[i] = false;
// deque functioneaza ca coada si stiva simultan
Deque<Integer> queue = new ArrayDeque<>();
// initial, coada contine doar start-ul
queue.addLast(start);
// marcam start-ul ca fiind vizitat (adaugat in coada)
viz[start] = true;
while (!queue.isEmpty()) {
// se ia urmatorul nod din coada
int nod = queue.removeFirst();
// verificam daca am ajuns la destinatie
if (nod == destinatie) return true;
// adaugam toate nodurile urmatoare posibile in coada
List<Integer> listaNodului = adjLists.get(nod);
for (int urm : listaNodului) {
// le sarim pe cele care sunt deja in coada
if (viz[urm]) continue;
// adaugam in coada si marcam ca vizitat
queue.addLast(urm);
viz[urm] = true;
}
}
return false;
}
}