[BOJ] 백준 [11266] 단절점 JAVA

[BOJ] 백준 [11266] 단절점 JAVA

import java.util. * ;

import java.io. * ;

import java.util.stream.Collectors;

public class Main {

static int V,E,order = 1 ,cnt = 0 ;

static int [] discover;

static ArrayList < Integer > [] list;

static boolean [] isCutVertex;

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

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

int [] input = Arrays.stream(br.readLine(). split ( " " )).mapToInt(Integer:: parseInt ).toArray();

V = input[ 0 ]; E = input[ 1 ];

list = new ArrayList[V + 1 ];isCutVertex = new boolean [V + 1 ];discover = new int [V + 1 ];

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

for ( int i = 1 ;i < = E;i + + ) {

input = Arrays.stream(br.readLine(). split ( " " )).mapToInt(Integer:: parseInt ).toArray();

list[input[ 0 ]]. add (input[ 1 ]); list[input[ 1 ]]. add (input[ 0 ]);

}

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

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

StringBuilder sb = new StringBuilder();

for ( int i = 1 ;i < = V;i + + ) {

if (isCutVertex[i]){

cnt + + ;

sb.append(i).append( " " );

}

}

System . out . println (cnt);

System . out . println (sb);

}

private static int dfs( int cur, boolean isRoot) {

discover[cur] = order + + ;

int ret = discover[cur];

int child = 0 ;

for ( int next : list[cur]) {

if (discover[next] = = 0 ) {

child + + ;

int prev = dfs(next, false );

if ( ! isRoot & & prev > = discover[cur])

isCutVertex[cur] = true ;

ret = Math.min(ret,prev);

} else

ret = Math.min(ret,discover[next]);

}

if (isRoot & & child > = 2 )

isCutVertex[cur] = true ;

return ret;

}

}

from http://katastrophe.tistory.com/70 by ccl(A) rewrite - 2021-10-31 17:00:36