Algorithms/DFSSCC.java at master · yusefabou/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
/* Counts strongly connected components */
import java.util.Scanner;
import java.io.*;
import java.lang.*;
import java.util.*;

class DFSSCC{
	static int[] pre;
	static int[] post;
	static int[] topArr;
	static int topCount;
	static int clock = 1;
	public static void main(String[] args){
		//Set up variables
		DFSSCC searcher = new DFSSCC();
		Scanner in = new Scanner(new InputStreamReader(System.in));
		int vertices = in.nextInt();
		int edges = in.nextInt();
		HashMap<Integer,LinkedList> graph = new HashMap<Integer,LinkedList>();
		HashMap<Integer,LinkedList> reverseGraph = new HashMap<Integer, LinkedList>();
		boolean[] visited = new boolean[vertices+1];
		Integer v1;
		Integer v2;
		topArr = new int[vertices+1];
		topCount = topArr.length - 1;
		pre = new int[vertices+1];
	    post = new int[vertices+1];
	    int sccnum  = 0; //Number of strongly connected components

		//Build a graph
		for(int i = 0; i < edges; i++){
			v1 = new Integer(in.nextInt());
			v2 = new Integer(in.nextInt());
			visited[v1.intValue()] = false;
			visited[v2.intValue()] = false;
			LinkedList list1 = new LinkedList();
			LinkedList listr = new LinkedList();

			if(graph.containsKey(v1)){
				list1 = graph.get(v1);
				list1.add(v2);
				graph.put(v1,list1);
			}
			if(reverseGraph.containsKey(v2)){
				listr = reverseGraph.get(v2);
				listr.add(v1);
				reverseGraph.put(v2,listr);
			}
			if(!graph.containsKey(v1)){
				list1.add(v2);
				graph.put(v1,list1);
			}
			if(!reverseGraph.containsKey(v2)){
				listr.add(v1);
				reverseGraph.put(v2,listr);
			}
		}

		//Part 1: Run DFS on Reverse Graph
		Integer u;
		for(int i = 1; i < visited.length; i++){
			u = new Integer(i);
			if(visited[i] == false){
				searcher.explore(u, reverseGraph, visited);
			}
		}

		//Reset visited
		for(int i = 1; i < visited.length; i++){
			visited[i] = false;
		}

		//Part 2: Count connected components on G. Process vertices in decreasing order
		//of post numbers
		for(int i = 1; i < topArr.length; i++){
			u = new Integer(topArr[i]);
			if(visited[topArr[i]] == false){
				sccnum++;
				searcher.exploreCC(u, graph, visited);
			}
		}
		System.out.println(sccnum);

	}

	public void explore(Integer u, HashMap<Integer,LinkedList> graph, boolean[] visited){
		visited[u.intValue()] = true;
		previsit(u);
		LinkedList list = new LinkedList();
		if(graph.containsKey(u)){
			list = graph.get(u);
			int listSize = list.size();
			Iterator<Integer> iter = list.iterator();

			for(int i = 0; i < listSize; i++){
				Integer cur = iter.next();
				if(visited[cur.intValue()] == false)
					this.explore(cur, graph, visited);
			}
		}
		postvisit(u);
	}

	public void exploreCC(Integer u, HashMap<Integer,LinkedList> graph, boolean[] visited){
		visited[u.intValue()] = true;
		LinkedList list = new LinkedList();
		if(graph.containsKey(u)){
			list = graph.get(u);
			int listSize = list.size();
			Iterator<Integer> iter = list.iterator();
			for(int i = 0; i < listSize; i++){
				Integer cur = iter.next();
				if(visited[cur.intValue()] == false){
					this.exploreCC(cur, graph, visited);
				}
			}

		}
	}

	public void previsit(Integer u){
		this.pre[u] = this.clock;
		this.clock = this.clock + 1;
	}

	public void postvisit(Integer u){
		this.post[u] = this.clock;
		this.topArr[this.topCount] = u.intValue();
		this.topCount = this.topCount - 1;
		this.clock = this.clock + 1;
	}
}