Cod sursa(job #1693101)

Utilizator superstar1998Moldoveanu Vlad superstar1998 Data 22 aprilie 2016 13:38:33
Problema Parcurgere DFS - componente conexe Scor 80
Compilator java Status done
Runda Arhiva educationala Marime 0.93 kb
import java.io.FileInputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
	static int count=0;
	static LinkedList<Integer>[] G;
	static int n,m;
	static boolean[] use;
	public static void main(String[] args) throws IOException{
		Scanner in = new Scanner(new FileInputStream("dfs.in"));
		PrintWriter out = new PrintWriter("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);
	}

}