Cod sursa(job #1705404)

Utilizator Osman_RuxandraOsman Maria - Ruxandra Osman_Ruxandra Data 20 mai 2016 15:25:30
Problema Parcurgere DFS - componente conexe Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 2.48 kb
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Iterator;
import java.util.Stack;


public class Main {
	
	private static int N, M, node1, node2;
	private static List adjList[];
	private static int parent[];
	private static int nrConnex = 0;
	private static int visited[];
	
	
	private static void readData() throws IOException {
		BufferedReader bf = new BufferedReader(new FileReader("dfs.in"));
		String tmp[] = bf.readLine().split(" ");
        N = Integer.parseInt(tmp[0]);
        M = Integer.parseInt(tmp[1]);
//		System.out.println("N: " + N);
//		System.out.println("M: " + M);
		
		//initializare vector de parinti
		parent = new int[N + 1];
		for(int i = 1; i <= N; i ++) {
			parent[i] = 0;
		}
		
		//initializare vector de adiacenta
		adjList = new List[N + 1];
		for(int i = 1; i <= N; i ++) {
			adjList[i] = new List(N);
		}
		
		//initalizare vector de vizitari
		//negru = 2; gri = 1; alb = 0
		visited = new int[N + 1];
		for(int i = 1; i <= N; i ++) {
			visited[i] = 0;
		}
		
		for(int i = 0; i < M; i ++) {
			tmp = bf.readLine().split(" ");
	        node1 = Integer.parseInt(tmp[0]);
	        node2 = Integer.parseInt(tmp[1]);
//			System.out.println("node1: " + node1);
//			System.out.println("node2: " + node2);
			Pair p = new Pair(node1, node2);
			adjList[p.node1].neighbors.add(p.node2);
			adjList[p.node2].neighbors.add(p.node1);
		}
		
//		System.out.println("Afisare vector de adiacenta: ");
//		for(int i = 1; i <=N; i ++) {
//			System.out.println(adjList[i].neighbors);
//		}
	}
	
	private static int DFS() {
		
		for(int i = 1; i <= N; i ++) {
			//daca nu a fost vizitat
			if(visited[i] == 0) {
				explore(i);
				nrConnex ++;
			}
		}
		return nrConnex;
	}
	
	private static void explore(int node) {
		//il fac gri
		visited[node] = 1;
		//pentru fiecare copil al sau
		Iterator<Integer> it = adjList[node].neighbors.listIterator();
		while(it.hasNext()) {
			int number = it.next();
			//daca este alb, ii marcam parintele si exploram noii copii
			if(visited[number] == 0) {
				parent[number] = node;
				explore(number);
			}
		}
		//il facem negru
		visited[node] = 2;
	}
	
	public static void main(String[] args) throws IOException {
		readData();
		int nr = DFS();
		PrintWriter pw = new PrintWriter("dfs.out");
		pw.println(nr);
		pw.close();
		//System.out.println("Avem " + nr + " componente conexe");
	}
}