[BOJ] 백준 [2150] 강한 결합 요소 JAVA

[BOJ] 백준 [2150] 강한 결합 요소 JAVA

import java.util. * ;

import java.io. * ;

public class Main{

static int V,E;

static boolean [] visit;

static ArrayList < Integer > [] list;

static ArrayList < Integer > [] listReverse;

static Stack < Integer > st;

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

init();

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

input = Arrays.stream(br.readLine(). split ( " " ))

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

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

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

}

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

if ( ! visit[i]) dfs(i);

visit = new boolean [V + 1 ];

int ret = 0 ;

list = new ArrayList[V + 1 ];

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

while ( ! st.isEmpty()){

Integer pop = st.pop();

if ( ! visit[pop]) reverseDfs(pop, + + ret);

}

TreeMap < Integer, ArrayList < Integer > > map = new TreeMap < > ();

list[ 1 ].sort((o1,o2) - > o1 - o2);

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

list[i].sort( new Comparator < Integer > () {

@Override

public int compare(Integer o1, Integer o2) {

return o1 - o2;

}

});

map.put(list[i].get( 0 ),list[i]);

}

System . out . println (ret);

map.entrySet().iterator().forEachRemaining(e - > {

e.getValue().forEach(l - > System . out . print (l + " " ));

System . out . println ( "-1" );

});

}

static void init() {

list = new ArrayList[V + 1 ];

listReverse = new ArrayList[V + 1 ];

visit = new boolean [V + 1 ];

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

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

st = new Stack < > ();

}

static void dfs( int cur){

visit[cur] = true ;

for (Integer next : list[cur]) {

if ( ! visit[next]) dfs(next);

}

st.push(cur);

}

static void reverseDfs( int cur, int cnt){

visit[cur] = true ;

for (Integer next : listReverse[cur]) {

if (visit[next]) continue ;

reverseDfs(next,cnt);

}

list[cnt]. add (cur);

}

}

from http://katastrophe.tistory.com/48 by ccl(A) rewrite - 2021-10-08 16:27:47