Cod sursa(job #1704423)

Utilizator bercarucostinBercaru Costin bercarucostin Data 18 mai 2016 19:28:19
Problema Parcurgere DFS - componente conexe Scor 60
Compilator java Status done
Runda Arhiva educationala Marime 1.74 kb
//package problemetest2;

import java.io.*;
import java.util.*;

 class Main {

	static ArrayList<ArrayList<Integer>> graf = new ArrayList<ArrayList<Integer>>();
	static int[] idx, lowlink, c;
	static int index;
	static int nr;
	static Stack s = new Stack();

	
	static public void CTC_Tarjan(){
		
		index = 0;
		for(int i = 1; i < idx.length; i ++)
			if(idx[i] == 0)
				Tarjan(i);
		
		
		return ;
	}
	
	static public int Tarjan(int v){
		
		idx[v] = index;
		lowlink[v] = index;
		index ++;
		s.push(v);
		int x;
		for(int u : graf.get(v)){
			if(idx[u] == 0){
				Tarjan(u);
				lowlink[v] = Math.min(lowlink[v], idx[u]);
			}else{
				if(s.contains(u)){
					lowlink[v] = Math.min(lowlink[v], idx[u]);
				}
			}
		}
		if(lowlink[v] == idx[v])
			nr++;
		do{
			x = (int) s.pop();
		}while (x != v);
		
		return v;
	}
	
	public static void main(String[] args) throws IOException {

		BufferedReader in = null;
		BufferedWriter out = null;
		in = new BufferedReader(new FileReader("dfs.in"));
		out = new BufferedWriter(new FileWriter("dfs.out"));

		String[] line = in.readLine().split(" ");
		int n = Integer.parseInt(line[0]);
		int m = Integer.parseInt(line[1]);
		int n1, n2;
		idx = new int[n + 1];
		lowlink = new int[n + 1];
		c = new int[n + 1];
		for (int i = 0; i < n + 1; i++)
			graf.add(i, new ArrayList<Integer>());
		for (int i = 0; i < m; i++) {
			line = in.readLine().split(" ");
			n1 = Integer.parseInt(line[0]);
			n2 = Integer.parseInt(line[1]);

			graf.get(Integer.parseInt(line[0])).add(Integer.parseInt(line[1]));
			graf.get(Integer.parseInt(line[1])).add(Integer.parseInt(line[0]));
		}
		CTC_Tarjan();
		out.write(String.valueOf(nr));
		in.close();
		out.close();
	}
}