[BOJ] 20647. Cowntagion (Graph)

[BOJ] 20647. Cowntagion (Graph)

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 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88

import java.io. * ; import java.util. * ; public class Main { FastScanner in ; PrintWriter out ; static int N, a, b, cntAdjacentLoads[]; void solve() { N = in .nextInt(); cntAdjacentLoads = new int [N + 1 ]; for ( int i = 0 ; i < N - 1 ; i + + ) { a = in .nextInt(); b = in .nextInt(); cntAdjacentLoads[a] + + ; cntAdjacentLoads[b] + + ; } int day = 0 ; for ( int i = 1 ; i < = N; i + + ) { if (cntAdjacentLoads[i] > 1 ) { // 연결된 길이 있을 경우 (자식 노드가 있을 경우) if (i ! = 1 ) cntAdjacentLoads[i] - - ; // 부모 노드는 이미 방문하였으므로 제외 (root 노드는 부모 노드가 없으므로 pass) int infectedCow = 1 ; // 감염된 소 while (infectedCow < cntAdjacentLoads[i] + 1 ) { // 연결된 농장의 개수(+1은 현재 농장)만큼 감염된 소 증가 infectedCow * = 2 ; // 해당 농장에서 감염 소 2배 증가 + + day; } } if (i ! = 1 ) day + + ; // 감염된 소 한 마리가 인접 농장으로 이동하는 이벤트 } out . println (day); } void run() { in = new FastScanner(); out = new PrintWriter( System . out ); solve(); out .close(); } public static void main( String [] args) { new Main().run(); } class FastScanner { BufferedReader br; StringTokenizer st; public FastScanner() { br = new BufferedReader( new InputStreamReader( System . in )); } public FastScanner( String s) { try { br = new BufferedReader( new FileReader(s)); } catch (FileNotFoundException e) { e.printStackTrace(); } } String nextToken() { while (st = = null | | ! st.hasMoreElements()) { try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); } int nextInt() { return Integer. parseInt (nextToken()); } long nextLong() { return Long.parseLong(nextToken()); } double nextDouble() { return Double.parseDouble(nextToken()); } } } Colored by Color Scripter

from http://data-make.tistory.com/683 by ccl(A) rewrite - 2021-08-25 01:27:01