Pagini recente » Cod sursa (job #603548) | Cod sursa (job #1857933) | Cod sursa (job #816860) | Cod sursa (job #449899) | Cod sursa (job #2631733)
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.util.Scanner;
import java.util.Vector;
public class DFS {
public static class Nod {
int indice=0;
int nrVecini=0;
Vector<Nod> vecini = new Vector<Nod>();
boolean vizitat=false;
}
public static void dfs(Nod nodCurent, PrintStream out) {
nodCurent.vizitat=true;
for(int i=0; i<nodCurent.nrVecini; i++) {
Nod vecin = nodCurent.vecini.get(i);
if(vecin.vizitat==false) {
dfs(vecin, out);
}
}
}
public static void main(String[] args) {
try {
Scanner scan = new Scanner(new File("dfs.in"));
PrintStream out = new PrintStream(new File("dfs.out"));
int n = scan.nextInt();
int m = scan.nextInt();
Nod[] graph = new Nod[n];
for(int i=0; i<n; i++) {
graph[i] = new Nod();
graph[i].indice=i;
}
for(int i=1; i<=m; i++) {
int x = scan.nextInt();
int y = scan.nextInt();
x--;
y--;
graph[x].vecini.add(graph[y]);
graph[y].vecini.add(graph[x]);
graph[x].nrVecini++;
graph[y].nrVecini++;
}
int nrComponenteConexe=0;
for(int i=0; i<n; i++) {
if(graph[i].vizitat==false) {
dfs(graph[i], out);
nrComponenteConexe++;
}
}
out.print(nrComponenteConexe);
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}