Cod sursa(job #1704320)

Utilizator roxana.maria3Roxana Domnisoru roxana.maria3 Data 18 mai 2016 16:40:20
Problema Parcurgere DFS - componente conexe Scor 70
Compilator java Status done
Runda Arhiva educationala Marime 3.31 kb
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class Main {
	private int V, E;
	private int T;
	int s;
	private ArrayList<HashSet<Integer>> edges;
	boolean[] visited;
	int[] level;
	int[] children;
	
	public Main(){
		edges = new ArrayList<HashSet<Integer>>();
	}
	
	public void insertEdge(int u, int v){
		edges.get(u).add(v);
		edges.get(v).add(u);
	}
	
	public HashSet<Integer> getEdges(int u){
		return edges.get(u);
	}
	
	public void readInitData(Scanner in){
		T = in.nextInt();
	}
	
	public void readData(Scanner in){
		int u, v;
		
		V = in.nextInt();
		E = in.nextInt();
	//	s = in.nextInt();
		
		visited = new boolean[V+1];
		level = new int[V+1];
		children = new int[V+1];
		
		for(int i=0; i<=V; i++){
			edges.add(i, new HashSet<Integer>()); 
		}

		for(int i=0; i< E; i++){
			u = in.nextInt();
			v = in.nextInt();
			insertEdge(u, v);
		}
		
	//	s = in.nextInt();
	}
	
	public void resetVisited(){
		for(int i=1; i<=V; i++)
			visited[i] = false;
	}
	
	public void resetLevel(){
		for(int i=1; i<=V; i++)
			level[i] = -1;
	}
	
	public void resetChildren(){
		for(int i=1; i<=V; i++)
			children[i] = -1;
	}
	
	public void BFS(){
		Queue<Integer> q = new LinkedList<Integer>();
		int lev = 0;
		resetLevel();
		resetVisited();
		
		level[s] = lev;
		q.add(s);
		visited[s] = true;
		
		while(!q.isEmpty()){
			int u = q.poll();
			lev = level[u] + 1;
			HashSet<Integer> neigh = getEdges(u);
			for(Integer v : neigh){
				if(!visited[v]){
					visited[v] = true;
					level[v] = lev;
					q.add(v);
				}
			}
		}
	}
	
	
	public void DFS(int s){
		Stack<Integer> q = new Stack<Integer>();
	
		q.push(s);
		visited[s] = true;
		
		while(!q.isEmpty()){
			int u = q.pop();
			HashSet<Integer> neigh = getEdges(u);
			for(Integer v : neigh){
				if(!visited[v]){
					visited[v] = true;
					q.add(v);
				}
			}
		}
	}
	
	public void numCompCnx() throws FileNotFoundException{
		PrintWriter out = new PrintWriter("dfs.out");
		int count = 0;
		for(int i=1; i<=V; i++){
			if(!visited[i]){
				count++;
				DFS(i);
			}
		}
		out.println(count);
		out.close();
	}
	
	public void count_children(){
		resetVisited();
		resetChildren();
		for(int i=1; i<=V; i++){
			if(!visited[i])
				children[i]  = count(i);
		}
	}
	
	public int count(int u){
		children[u] = 1;
		visited[u] = true;
		HashSet<Integer> neigh = getEdges(u);
		for(Integer v : neigh){
			if(!visited[v])
				children[u] += count(v);
		}
		return children[u];
		
	}
	public void printSolution2() throws FileNotFoundException{
		int count = 0;
		PrintWriter out = new PrintWriter("dfs.out");
		for(int i=1; i<=V; i++){
	//		System.out.print("(" + i + " " + children[i] + ")");
			if(children[i] % 2 == 0 && children[i] != 2)
				count++;
		}
		out.println(count);
		out.close();
	}
	
	public void printSolution() throws FileNotFoundException{
		PrintWriter out = new PrintWriter("bfs.out");
		for(int i=1; i<=V; i++){
		//	if(i != s)
				out.print(level[i] + " ");
		}
		out.close();
	}
	
	public static void main(String[] args) throws FileNotFoundException {
		Main g = new Main();
		Scanner in = new Scanner(new FileReader("dfs.in"));
		g.readData(in);
		g.numCompCnx();
		
		in.close();
	}
}