Cod sursa(job #1431015)

Utilizator Florea_Anda_Madalina_321CBFlorea Anda-Madalina Florea_Anda_Madalina_321CB Data 8 mai 2015 22:59:25
Problema Parcurgere DFS - componente conexe Scor 20
Compilator java Status done
Runda Arhiva educationala Marime 1.64 kb
//package pregTest;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Vector;

public class Main {
	public static Vector<ArrayList<Integer>> liste = null;
	public static int n,m;
	public static final int nmax = 100001;
	public static boolean vizitat[];
	public static void main(String[] args) {

		// TODO Auto-generated constructor stub
		
		try {
			Scanner fileScanner = new Scanner(new FileInputStream("dfs.in"));
			n = fileScanner.nextInt();
			m = fileScanner.nextInt();
			liste = new Vector<ArrayList<Integer>>(n + 1);
			for (int i = 0; i <= n; i++) {
				liste.add(i, new ArrayList<Integer>());
			}
			for (int i = 0; i < m; i++) {
				int n1 = fileScanner.nextInt();
				int n2 = fileScanner.nextInt();
				liste.get(n1).add(n2);
				liste.get(n2).add(n1);

			}
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		vizitat= new boolean[n];
		int nr = 0;
		for (int i = 0; i < n; i++) {
			if (vizitat[i] != true) {
				dfs(i,vizitat);
				nr++;
			}
		}
		try {
			PrintWriter writer = new PrintWriter("dfs.out");
			writer.write(String.valueOf(nr));
			writer.close();
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
	}

	private static void dfs(int i,
			boolean[] vizitat) {
		// TODO Auto-generated method stub
		vizitat[i] = true;
		for (int vecin : (liste.get(i))) {
			if (!vizitat[vecin]) {
				vizitat[vecin] = true;
				dfs(vecin,vizitat);
			}
		}

	}

}