1+ class SCC {
2+
3+ static class Edge {
4+ int from , to ;
5+ public Edge (int from , int to ) {
6+ this .from = from ; this .to = to ;
7+ }
8+ }
9+
10+ final int n ;
11+ int m ;
12+ final java .util .ArrayList <Edge > unorderedEdges ;
13+ final int [] start ;
14+
15+ public SCC (int n ) {
16+ this .n = n ;
17+ this .unorderedEdges = new java .util .ArrayList <>();
18+ this .start = new int [n + 1 ];
19+ }
20+
21+ public void addEdge (int from , int to ) {
22+ unorderedEdges .add (new Edge (from , to ));
23+ start [from + 1 ]++;
24+ this .m ++;
25+ }
26+
27+ public int [][] build () {
28+ for (int i = 1 ; i <= n ; i ++) {
29+ start [i ] += start [i - 1 ];
30+ }
31+ Edge [] orderedEdges = new Edge [m ];
32+ int [] count = new int [n + 1 ];
33+ System .arraycopy (start , 0 , count , 0 , n + 1 );
34+ for (Edge e : unorderedEdges ) {
35+ orderedEdges [count [e .from ]++] = e ;
36+ }
37+ int nowOrd = 0 ;
38+ int groupNum = 0 ;
39+ int k = 0 ;
40+ // parent
41+ int [] par = new int [n ];
42+ int [] vis = new int [n ];
43+ int [] low = new int [n ];
44+ int [] ord = new int [n ];
45+ int [] ids = new int [n ];
46+ java .util .Arrays .fill (ord , -1 );
47+ // u = lower32(stack[i]) : visiting vertex
48+ // j = upper32(stack[i]) : jth child
49+ long [] stack = new long [n ];
50+ // size of stack
51+ int ptr = 0 ;
52+ // non-recursional DFS
53+ for (int i = 0 ; i < n ; i ++) {
54+ if (ord [i ] >= 0 ) continue ;
55+ par [i ] = -1 ;
56+ // vertex i, 0th child.
57+ stack [ptr ++] = 0l << 32 | i ;
58+ // stack is not empty
59+ while (ptr > 0 ) {
60+ // last element
61+ long p = stack [--ptr ];
62+ // vertex
63+ int u = (int ) (p & 0xffff_ffffl );
64+ // jth child
65+ int j = (int ) (p >>> 32 );
66+ if (j == 0 ) { // first visit
67+ low [u ] = ord [u ] = nowOrd ++;
68+ vis [k ++] = u ;
69+ }
70+ if (start [u ] + j < count [u ]) { // there are more children
71+ // jth child
72+ int to = orderedEdges [start [u ] + j ].to ;
73+ // incr children counter
74+ stack [ptr ++] += 1l << 32 ;
75+ if (ord [to ] == -1 ) { // new vertex
76+ stack [ptr ++] = 0l << 32 | to ;
77+ par [to ] = u ;
78+ } else { // backward edge
79+ low [u ] = Math .min (low [u ], ord [to ]);
80+ }
81+ } else { // no more children (leaving)
82+ while (j --> 0 ) {
83+ int to = orderedEdges [start [u ] + j ].to ;
84+ // update lowlink
85+ if (par [to ] == u ) low [u ] = Math .min (low [u ], low [to ]);
86+ }
87+ if (low [u ] == ord [u ]) { // root of a component
88+ while (true ) { // gathering verticies
89+ int v = vis [--k ];
90+ ord [v ] = n ;
91+ ids [v ] = groupNum ;
92+ if (v == u ) break ;
93+ }
94+ groupNum ++; // incr the number of components
95+ }
96+ }
97+ }
98+ }
99+ for (int i = 0 ; i < n ; i ++) {
100+ ids [i ] = groupNum - 1 - ids [i ];
101+ }
102+
103+ int [] counts = new int [groupNum ];
104+ for (int x : ids ) counts [x ]++;
105+ int [][] groups = new int [groupNum ][];
106+ for (int i = 0 ; i < groupNum ; i ++) {
107+ groups [i ] = new int [counts [i ]];
108+ }
109+ for (int i = 0 ; i < n ; i ++) {
110+ int cmp = ids [i ];
111+ groups [cmp ][--counts [cmp ]] = i ;
112+ }
113+ return groups ;
114+ }
115+ }
0 commit comments