[백준 9470] Strahler 순서 (Java)

문제 링크: https://www.acmicpc.net/problem/9470

9470번: Strahler 순서

1. 주의할 점

- 매 TC마다 초기화 작업을 수행한다

- Stahler가 1 늘어나는 기준을 이해한다

 

2. 구현

- 모든 간선에 대한 정보를 Li[] 에 담는다

- Conn[] 배열을 통해 해당 Node로 도착하는 Node의 수를 저장한다

- Counting[]을 통해 각 Node에 도착한 Stahler 번호를 저장한다. 이때 Stahler번호가 1개도 없었다면 추가, 1개라도 있었을 경우, 비교하여 가장 큰 값을 저장하도록 한다

- Conn[next]==0이면 다음 Node도 큐에 넣고 Counting[] 값을 조건에 따라 수정 혹은 유지한다

 

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    static int node,edge,testNum,answer;
    static int conn[];
    static List<Integer> li[],counting[];
    
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    int test = Integer.parseInt(br.readLine().trim());
	    for(int t=1;t<=test;t++){
	        StringTokenizer st = new StringTokenizer(br.readLine());
	        testNum = Integer.parseInt(st.nextToken());
	        node = Integer.parseInt(st.nextToken());
	        edge = Integer.parseInt(st.nextToken());
	        
	        //초기화
	        answer=1;
	        conn = new int[node+1];
	        li = new List[node+1];
	        counting = new List[node+1];
	        for(int i=1;i<=node;i++){
	            li[i]=new ArrayList<>();
	            counting[i]=new ArrayList<>();
	        }
	        for(int i=0;i<edge;i++){
	            st = new StringTokenizer(br.readLine());
    	        int from = Integer.parseInt(st.nextToken());
    	        int to = Integer.parseInt(st.nextToken());
    	        li[from].add(to);
    	        conn[to]++;
	        }
	        Queue<Integer> q = new LinkedList<>();
	        for(int i=1;i<=node;i++){
	            if(conn[i]==0){
	                counting[i].add(1);
	                q.offer(i);
	            }
	        }
	        
	        while(!q.isEmpty()){
	            int cidx = q.poll();
	            int cv = counting[cidx].get(0);
	            answer = Math.max(answer,cv);
	            for(int i=0;i<li[cidx].size();i++){
	                int next = li[cidx].get(i);
	                if(counting[next].isEmpty()) counting[next].add(cv);
	                else{
	                    if(counting[next].get(0)==cv) counting[next].add(cv);
	                    else if(counting[next].get(0)<cv){
	                        counting[next].clear();
	                        counting[next].add(cv);
	                    }
	                }
	                if(--conn[next]==0){
	                    q.offer(next);
	                    if(counting[next].size()>1){
	                        int val = counting[next].get(0);
	                        counting[next].clear();
	                        counting[next].add(val+1);
	                    }
	                }
	            }
	        }
	        System.out.println(testNum+" "+answer);
	    }
	}
}