Cod sursa(job #1430865)

Utilizator julia11Julia Adela julia11 Data 8 mai 2015 21:31:31
Problema Parcurgere DFS - componente conexe Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 1.25 kb
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;


public class Dfs {
	
	static int [][] adjMat;
	static int n;
	static int [] visited;
	
	public Dfs(int n){
		this.n = n;

		adjMat = new int[n+1][n+1];
		visited = new int[n+1];
	}
	
	static void dfs(int source){
		
		visited[source] = 1;

		for (int i = 1; i <= n; i++) {
			if(visited[i] == 0 && adjMat[source][i] == 1){
				dfs(i);
			}
		}
	}

	public static void main(String[] args) throws IOException {
		
        Scanner in = new Scanner(new FileReader("dfs.in"));
        
        int n =in.nextInt();
        int m = in.nextInt();    
        int k=0,x,y;

        Dfs main = new Dfs(n);
        
        for (int i = 0; i < m; i++) {
        	x = in.nextInt();
        	y = in.nextInt();

			adjMat[x][y] = 1;
			adjMat[y][x] = 1;
		}  
        
        in.close();
        
        for (int i = 1; i <= n; i++) {
			if(visited[i] == 0){
				System.out.println("Apelex dfs din: " + i);
				dfs(i);
				k++;
			}
		}
        
         
        BufferedWriter out = new BufferedWriter(new FileWriter("dfs.out"));
        out.append(k + "\n");
        out.close();
		
	}
	
}