Cod sursa(job #1705803)

Utilizator CristianVijaeacVijaeac Cristian-Octavian CristianVijaeac Data 20 mai 2016 23:36:52
Problema Parcurgere DFS - componente conexe Scor 100
Compilator java Status done
Runda Arhiva educationala Marime 2.27 kb

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class Main {
	
	
	static int numEdges;
	static int numNodes;
	static int source;
	static boolean[] isVisited;


	public static void dfs(ArrayList<ArrayList<Integer>> edge,int source){
		
		Stack<Integer> s = new Stack<Integer>();
		s.push(source);
		isVisited[source] = true;
	
		while(!s.isEmpty()){
			
			int n = s.pop();
			ArrayList<Integer> neighbour = edge.get(n);
			for (Integer e : neighbour){
				
				if (!isVisited[e]){
					isVisited[e] = true;
					s.push(e);
				}
			}
			
		}
		

	
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		BufferedReader in = null;
		ArrayList<ArrayList<Integer>> edges = new ArrayList<ArrayList<Integer>>();		
		int result=0;
		
		
		try {
			in = new BufferedReader(new FileReader("dfs.in"));
			String[] aux = in.readLine().split(" ");
			numNodes = Integer.parseInt(aux[0]);
			numEdges = Integer.parseInt(aux[1]);	
			
			isVisited = new boolean[numNodes];
			for (int i=0;i<numNodes;i++)
				isVisited[i] = false;
	
			for (int i=0;i<numNodes;i++)
				edges.add(new ArrayList<Integer>());
			
			for (int i = 0 ; i < numEdges ; i++){
				
				aux = in.readLine().split(" ");
				int s = Integer.parseInt(aux[0])-1;
				int e = Integer.parseInt(aux[1])-1;
				edges.get(s).add(e);
				edges.get(e).add(s);
			}
			
			for (int i=0;i<numNodes;i++){
				if (!isVisited[i]){
					result++;
					dfs(edges,i);
				
				}
			}	
		} catch (IOException e) {
			e.printStackTrace();
		
		} finally {
			if (in != null) {
		
				try {
					in.close();
				
				} catch (IOException e) {

				}
			}
		}
		
		try {
			BufferedWriter bufferedOut = new BufferedWriter( new FileWriter("dfs.out"));
			PrintWriter out = new PrintWriter(bufferedOut);
	
		
			out.print(result);
			System.out.println(result);
		
	
		out.close();
		bufferedOut.close();
	
	} catch (IOException e) {
		e.printStackTrace();
	}
		
		
	
	}
}