[BOJ] 백준 [4196] 도미노 JAVA

[BOJ] 백준 [4196] 도미노 JAVA

import java.util. * ;

import java.io. * ;

import java.util.stream. * ;

public class Main {

static boolean [] finished;

static int n,m,index,sccIndex;

static int [] discover,inDegree,sccNum;

static ArrayList < ArrayList < Integer > > list;

static Stack < Integer > st;

public static void main( String [] args) throws IOException {

BufferedReader br = new BufferedReader( new InputStreamReader( System . in ));

int tc = Integer. parseInt (br.readLine());

while (tc - - > 0 ){

String [] input = br.readLine(). split ( " " );

n = Integer. parseInt (input[ 0 ]);

m = Integer. parseInt (input[ 1 ]);

list = new ArrayList < > ();

for ( int i = 0 ;i < = n;i + + ) list. add ( new ArrayList < > ());

for ( int i = 0 ;i < m;i + + ){

int [] edge = Arrays.stream(br.readLine(). split ( " " ))

.mapToInt(Integer:: parseInt ).toArray();

list.get(edge[ 0 ]). add (edge[ 1 ]);

}

findScc();

setInDegree();

System . out . println (getZeroInDegree());

}

}

private static int getZeroInDegree() {

int ans = 0 ;

for ( int i = 1 ;i < = sccIndex;i + + )

if (inDegree[i] = = 0 ) ans + + ;

return ans;

}

private static void setInDegree() {

inDegree = new int [sccIndex + 1 ];

for ( int i = 1 ;i < = n;i + + )

for (Integer next : list.get(i))

if (sccNum[i] ! = sccNum[next]) inDegree[sccNum[next]] + + ;

}

private static void findScc() {

index = 0 ;

discover = new int [n + 1 ];

finished = new boolean [n + 1 ];

st = new Stack < > ();

sccIndex = 0 ;

sccNum = new int [n + 1 ];

for ( int i = 1 ;i < = n;i + + )

if (discover[i] = = 0 ) dfs(i);

}

private static int dfs( int cur) {

discover[cur] = + + index;

st.push(cur);

int parent = discover[cur];

for (Integer next : list.get(cur)) {

if (discover[next] = = 0 ) parent = Math.min(dfs(next),parent);

else if ( ! finished[next]) parent = Math.min(discover[next],parent);

}

if (parent = = discover[cur]){

while ( true ){

Integer pop = st.pop();

finished[pop] = true ;

sccNum[pop] = sccIndex + 1 ;

if (pop = = cur) break ;

}

sccIndex + + ;

}

return parent;

}

}

from http://katastrophe.tistory.com/88 by ccl(A) rewrite - 2021-11-23 16:00:28