Cod sursa(job #1430891)

Utilizator julia11Julia Adela julia11 Data 8 mai 2015 21:50:01
Problema Parcurgere DFS - componente conexe Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 1.67 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 Main {
     
	static ArrayList<ArrayList<Integer>> list;
    static int n;
    static int [] visited;
     
    public Main(int n){
        this.n = n;
 
		list = new ArrayList<ArrayList<Integer>>(n+1);
		for (int i = 0; i <= n; i++) {
			list.add(new ArrayList<Integer>());
		}

        visited = new int[n+1];
    }
     
    static void dfs(int source){
         
        visited[source] = 1;
 
        for (int i = 0; i < list.get(source).size(); i++) {
            if(visited[list.get(source).get(i)] == 0){
//            	System.out.println("Am gasit nevizitat " + i);
                dfs(list.get(source).get(i));
            }
        }
    }
 
    public static void main(String[] args) throws IOException {
         
        Scanner in = new Scanner(new FileReader("dfs"));
         
        int n =in.nextInt();
        int m = in.nextInt();    
        int k=0,x,y;
 
        Main main = new Main(n);
         
        for (int i = 0; i < m; i++) {
            x = in.nextInt();
            y = in.nextInt();
 
            list.get(x).add(y);
            list.get(y).add(x);
        }  
         
        in.close();

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