Cod sursa(job #1430914)

Utilizator Rotaru_Jeni_323CBRotaru Jeni Rotaru_Jeni_323CB Data 8 mai 2015 21:59:20
Problema Parcurgere DFS - componente conexe Scor 45
Compilator java Status done
Runda Arhiva educationala Marime 1.61 kb
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[1500][1500];
		
		int cnt=0;//nr. de componente tari conexe;
		int[] viz = new int[1500];//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();
	}

}