Pagini recente » Cod sursa (job #2686531) | Cod sursa (job #3289982) | Monitorul de evaluare | Cod sursa (job #1369915) | Cod sursa (job #1430968)
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Scanner;
public class Main {
public static void DFS(int nod, int[] viz, int n, int[][] matriceAdiacenta){
viz[nod]=1;//nodul a fost vizitat;
for(int i=1 ; i<=n ; i++){
if (viz[i]!=1 && matriceAdiacenta[nod][i]==1){
DFS(i, viz, n, matriceAdiacenta);
}
}
}
public static void main(String[] args) throws FileNotFoundException {
//Citirea datelor din fisier;
Scanner reader = new Scanner(new FileInputStream("dfs.in"));
int n = reader.nextInt(); //nr. de noduri;
int m = reader.nextInt(); //nr. de muchii;
int[][] matriceAdiacenta = new int[n+1][n+1];
int cnt=0;//nr. de componente tari conexe;
int[] viz = new int[n+1];//vectorul nodurilor viiztate;
//Crearea matricei de adiacenta;
while(reader.hasNextInt()){
int x = reader.nextInt();
int y = reader.nextInt();
//for (int j=1 ; j<=m ; j++){
matriceAdiacenta[x][y]=1;
matriceAdiacenta[y][x]=1;
//}
}
for (int i=1 ; i<=n ; i++){
if (viz[i]!=1){//nodul nu este vizitat;
cnt++;
DFS(i, viz, n, matriceAdiacenta);//aplic DFS;
}
}
/*System.out.println("Rezultatul citirii este: noduri= " + n + ", muchii= " + m);
for (int i=1 ; i<=n ; i++){
for (int j=1 ; j<=n ; j++){
System.out.print(matriceAdiacenta[i][j]);
}
System.out.println();
}
System.out.println("Rezultatul este: " + cnt);*/
PrintWriter writer = new PrintWriter("dfs.out");
writer.write(String.valueOf(cnt) + "\n");
writer.close();
reader.close();
}
}