백준 11437 공통조상 찾기.java

백준 11437 공통조상 찾기.java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

import java.util. * ; public class algotest { public static LinkedList < Integer > [] adjList; static int [] parent; static int [] depth; public static void main( String [] args){ Scanner sc = new Scanner ( System . in ); int N = sc.nextInt(); parent = new int [N + 1 ]; depth = new int [N + 1 ]; int a,b; adjList = new LinkedList[N + 1 ]; for ( int i = 1 ; i < = N; i + + ) { adjList[i] = new LinkedList < Integer > (); } for ( int i = 0 ; i < N - 1 ; i + + ) { a = sc.nextInt(); b = sc.nextInt(); adjList[a]. add (b); adjList[b]. add (a); } // DFS를 통해 깊이와 부모 노드 배열에 저장 dfs( 1 , 0 , - 1 ); int M = sc.nextInt(); for ( int i = 0 ; i < M; i + + ){ a = sc.nextInt(); b = sc.nextInt(); System . out . println (findSameParent(a,b)); } } private static int findSameParent( int a, int b) { while (depth[a] ! = depth[b]){ if (depth[a] > depth[b]){ a = parent[a]; } else { b = parent[b]; } } while (parent[a] ! = parent[b]){ a = parent[a]; b = parent[b]; } if (a = = b){ return a;} return parent[a]; } public static void dfs( int cur, int d, int p) { depth[cur] = d; parent[cur] = p; for ( int next : adjList[cur]) { if (next ! = p) { dfs(next, d + 1 , cur); } } } } Colored by Color Scripter

from http://javannspring.tistory.com/283 by ccl(A) rewrite - 2021-11-24 14:01:36