Cod sursa(job #1693084)

Utilizator superstar1998Moldoveanu Vlad superstar1998 Data 22 aprilie 2016 13:10:03
Problema Parcurgere DFS - componente conexe Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 0.94 kb
import java.io.File;
import java.io.IOException;
import java.util.Formatter;
import java.util.LinkedList;
import java.util.Scanner;

public class DFS {
	static int count=0;
	static LinkedList<Integer>[] G;
	static int n,m;
	static boolean[] use;
	@SuppressWarnings("unchecked")
	public static void main(String[] args) throws IOException{
		Scanner in = new Scanner(new File("dfs.in"));
		Formatter out = new Formatter("dfs.out");
		n=in.nextInt();
		m=in.nextInt();
		G = new LinkedList[n+1];
		for(int i=1;i<=n;i++)
			G[i]=new LinkedList<Integer>();
		use =  new boolean[n+1];
		int x,y;
		for(int i=1;i<=m;i++)
		{
			x=in.nextInt();
			y=in.nextInt();
			G[x].add(y);
			G[y].add(x);
		}
		for(int i=1;i<=n;i++)
			if(!use[i])
			{
				dfs(i);
				count++;
			}
		out.format("%d", count);
		in.close();
		out.close();
	}
	static void dfs(int x)
	{
		use[x]=true;
		for(Integer i:G[x])
			if(!use[i])dfs(i);
	}

}