Cod sursa(job #2631733)

Utilizator mirceaisherebina mircea mirceaishere Data 30 iunie 2020 19:15:10
Problema Parcurgere DFS - componente conexe Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 1.36 kb

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.util.Scanner;
import java.util.Vector;


public class DFS {
	
	public static class Nod {
		int indice=0;
		int nrVecini=0;
		Vector<Nod> vecini = new Vector<Nod>();
		boolean vizitat=false;
	}
	
	public static void dfs(Nod nodCurent, PrintStream out) {
		nodCurent.vizitat=true;
		for(int i=0; i<nodCurent.nrVecini; i++) {
			Nod vecin = nodCurent.vecini.get(i); 
			if(vecin.vizitat==false) {
				dfs(vecin, out);
			}
		}
	}
	
	public static void main(String[] args) {
		
		try {
			Scanner scan = new Scanner(new File("dfs.in"));
			PrintStream out = new PrintStream(new File("dfs.out"));
			
			int n = scan.nextInt();
			int m = scan.nextInt();
			Nod[] graph = new Nod[n];			
			for(int i=0; i<n; i++) {
				graph[i] = new Nod();
				graph[i].indice=i;
			}			
			for(int i=1; i<=m; i++) {
				int x = scan.nextInt();
				int y = scan.nextInt();
				x--;
				y--;
				graph[x].vecini.add(graph[y]);
				graph[y].vecini.add(graph[x]);
				graph[x].nrVecini++;
				graph[y].nrVecini++;
			}
			int nrComponenteConexe=0;
			for(int i=0; i<n; i++) {
				if(graph[i].vizitat==false) {
					dfs(graph[i], out);
					nrComponenteConexe++;
				}
			}
			out.print(nrComponenteConexe);
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}