Cod sursa(job #1555440)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 22 decembrie 2015 19:51:44
Problema Parcurgere DFS - componente conexe Scor 80
Compilator java Status done
Runda Arhiva educationala Marime 0.91 kb
import java.util.*;
import java.io.*;

public class Main
{
	static final int NMAX = 100005;
	static ArrayList<Integer>[] v = new ArrayList[NMAX];
	static int cnt;
	static boolean[] viz = new boolean[NMAX];

	public static void Dfs(int x)
	{
		viz[x] = true;
		for (Integer i : v[x])
			if (viz[i] == false)
				Dfs(i);
	}

	public static void main(String[] args) throws FileNotFoundException
	{
		int i, n, m, x, y;
		Scanner in = new Scanner(new FileInputStream("dfs.in"));
		
		for (i=0;i<NMAX;i++) v[i] = new ArrayList<Integer>();
		n = in.nextInt();
		m = in.nextInt();
			
		for (i = 1; i <= m; i++)
		{
			x = in.nextInt();
			y = in.nextInt();
			v[x].add(y);
			v[y].add(x);
		}

		for (i = 1; i <= n; i++)
			if (viz[i] == false)
				{
					cnt++;
					Dfs(i);
				}
		
		PrintWriter out = new PrintWriter("dfs.out");
		out.println(cnt);
		
		in.close();
		out.close();
	}
}