Cod sursa(job #1705349)

Utilizator deeagrtAndGrt deeagrt Data 20 mai 2016 12:43:59
Problema Parcurgere DFS - componente conexe Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 1.01 kb


import java.io.*;
import java.util.*;

public class Main {
	 static ArrayList<ArrayList<Integer>> adj;
	 static int[] visited ;
	
	public static void dfs(int n) {
		visited[n] = 1;
		for (Integer x : adj.get(n))
			if (visited[x] != 1)
				dfs(x);
		 
		 
	}
	public static void main(String[] args) throws IOException {
		 Scanner br= new Scanner(new BufferedInputStream(new FileInputStream("bfs.in")));
		 PrintStream out = new PrintStream(new FileOutputStream("bfs.out"));
		 
		 int n = br.nextInt();
		 int m =  br.nextInt();
		 adj = new ArrayList<ArrayList<Integer>>();
		 for ( int i = 1 ; i <= n + 1 ;i++)
			 adj.add(new ArrayList<Integer>());
		 
		 for (int i = 0 ; i < m ; i++){
			 int x =  br.nextInt();
			 int y =  br.nextInt();
			 adj.get(x).add(y);
			 }
		 
		 visited = new int[n + 1];
		 int comp = 0;
		 for (int i = 1; i <= n ; i++)
			 if (visited[i] != 1){
				 comp++;
				 dfs(i);
			 }
			out.println(comp);
			out.close();
			br.close();
		 
	}
}