[BOJ] 백준 [11400] 단절선 JAVA

[BOJ] 백준 [11400] 단절선 JAVA

import java.util. * ;

import java.io. * ;

import java.util.stream.Collectors;

public class Main {

static int V,E,order = 1 ;

static int [] discover;

static ArrayList < Integer > [] list;

static ArrayList < int [] > cutEdge = new ArrayList < > ();

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 ];

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, 0 );

cutEdge.sort((o1, o2) - > o1[ 0 ] ! = o2[ 0 ] ? o1[ 0 ] - o2[ 0 ] : o1[ 1 ] - o2[ 1 ]);

System . out . println (cutEdge.size());

for ( int [] edge : cutEdge)

System . out . println (edge[ 0 ] + " " + edge[ 1 ]);

}

private static int dfs( int cur, int parent) {

discover[cur] = order + + ;

int ret = discover[cur];

for ( int next : list[cur]) {

if (next = = parent) continue ;

if (discover[next] = = 0 ) {

int prev = dfs(next,cur);

if (prev > discover[cur])

cutEdge. add ( new int []{Math.min(cur,next), Math.max(cur,next)});

ret = Math.min(ret,prev);

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

}

return ret;

}

}

from http://katastrophe.tistory.com/71 by ccl(A) rewrite - 2021-10-31 19:26:35