[BOJ] 백준 [9466] 텀 프로젝트 JAVA

[BOJ] 백준 [9466] 텀 프로젝트 JAVA

import java.util. * ;

import java.io. * ;

import java.util.stream.Collectors;

public class Main {

static Stack < Integer > stack;

static ArrayList < ArrayList < Integer > > SCC;

static int N,index;

static int [] discover;

static boolean [] finish;

static ArrayList < Integer > [] list;

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 ){

N = Integer. parseInt (br.readLine());

int [] input = new int [N + 1 ];

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

for ( int i = 1 ;i < = N;i + + ) input[i] = Integer. parseInt (e[i - 1 ]);

init();

for ( int i = 1 ;i < = N;i + + ) list[i]. add (input[i]); // 그래프 연결

for ( int i = 1 ;i < = N;i + + ) if (discover[i] = = 0 ) dfs(i);

int notTeam = N;

for (ArrayList < Integer > scc : SCC) {

if (scc.size() > = 2 | | scc.size() = = 1 & & input[scc.get( 0 )] = = scc.get( 0 )){

notTeam = notTeam - scc.size();

}

}

System . out . println (notTeam);

}

}

private static void init() {

index = 0 ;

stack = new Stack < > ();

discover = new int [N + 1 ];

list = new ArrayList[N + 1 ];

finish = new boolean [N + 1 ];

SCC = new ArrayList < > ();

for ( int i = 1 ;i < = N;i + + ) list[i] = new ArrayList < > ();

}

private static int dfs( int cur) {

discover[cur] = + + index;

stack.push(cur);

int parent = discover[cur];

for (Integer next : list[cur]) {

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

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

}

if (parent = = discover[cur]){

ArrayList < Integer > scc = new ArrayList < > ();

while ( true ){

Integer pop = stack.pop();

scc. add (pop);

finish[pop] = true ;

if (pop = = cur) break ;

}

SCC. add (scc);

}

return parent;

}

}

from http://katastrophe.tistory.com/53 by ccl(A) rewrite - 2021-10-17 18:00:32