Cod sursa(job #1703777)

Utilizator ElionIonescu Elena Elion Data 17 mai 2016 17:12:08
Problema Parcurgere DFS - componente conexe Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 1.29 kb
package dfs;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	
	int n, m;
	ArrayList<ArrayList<Integer>> listaAdj;
	
	ArrayList<Integer> vizitat;
	
	Main(){
		listaAdj = new ArrayList<ArrayList<Integer>>();
		vizitat = new ArrayList<Integer>();		
	}
	
	public void readData() throws FileNotFoundException{
		Scanner s = new Scanner(new File("dfs.in"));
		
		n = s.nextInt();
		m = s.nextInt();
		
		// Initializari
		for(int i = 0; i < n; i ++){
			listaAdj.add(new ArrayList<Integer>());
			vizitat.add(0);
		}
		
		// Formez graful
		for(int i = 0; i < m; i++){
			int nod1 = s.nextInt();
			int nod2 = s.nextInt();
			
			listaAdj.get(nod1-1).add(nod2);		
		}
	}
	
	public int connectedComponents(){
		
		int nr = 0;
		for(int i = 0; i < n; i++){
			if(vizitat.get(i) ==  0){
				nr++;
				dfs(i);
			}
		}
		
		return nr;
	}
	
	public void dfs(int root){
		
		if(vizitat.get(root) == 0){
			vizitat.set(root, 1);
			for(Integer child : listaAdj.get(root)){
				dfs(child);
			}
		}
	}
	
	public static void main(String[] args) throws FileNotFoundException {
		Main s = new Main();
		
		s.readData();
		
		System.out.println(s.connectedComponents());
		
		
	}
}