Pagini recente » Cod sursa (job #3159513) | Cod sursa (job #2764063) | Cod sursa (job #522567) | Cod sursa (job #104122) | Cod sursa (job #1703753)
package dfs;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;
public class Solution_dfs {
int n, m;
ArrayList<ArrayList<Integer>> listaAdj;
ArrayList<Integer> vizitat;
Solution_dfs(){
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 {
Solution_dfs s = new Solution_dfs();
s.readData();
System.out.println(s.connectedComponents());
}
}