BOJ 6415-は木ですか?

質問する

問題に答える

に近づく

この問題をするとき、最初は木の周りを回らないようにしたいと思っていました.しかし,問題ではルートノードは与えられていないので,巡回する前にルートノードを見つけるべきである.しかし問題そのものが木かどうかを判断すればよいので,必ずしも巡回しなくても木の特徴を利用すればより容易に解くことができる.最終的に私は巡り方ではなく、木の特徴で問題を解きます.
前に木の特徴について書いたので、その文章を参考にしてほしいです.(しかし実際には、これらの特徴を完全に問題に書いています)
ツリーフィーチャー
1.ルートノードは、ノード自体が存在しない場合は、1つまたは存在しない必要があります.
2.ルートノードから他の任意のノードへのパスは一意です.
3.ノード数-1=幹線数
そこでroot,children集合を作成しました.ルートセットは、開始ノードとして使用できるノードの集合であり、サブセットは、サブノードとして使用されるノードの集合である.次に、入力を受信すると、条件に基づいてルートセットとサブセットを演算し、ツリーを接続します.
1つのケースの入力がすべて受信された場合、ツリーを判別できます.
入力ノードが1つ以上ある場合、
ルートセットにノードが1つしか存在せず、幹線数+1=ルートセットのサイズ+サブセットのサイズを満たす場合は、ツリーです.
入力にノードが入力されていない場合は、ツリーを直接満たします.
この条件に基づいて,木の特徴に合致するかどうかを決定し,答えを出力すればよい.
*この問題の入力処理は難しいです.あなたがゆっくり寝ているのは知っていたのに、Scannerと書いて...ほほほ

プールコード

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 입력
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        boolean flag = true;
        int caseN = 0; // 몇 번째 나무인지 기록

        while(flag){
            HashSet<Integer> root = new HashSet<Integer>();
            HashSet<Integer> children = new HashSet<Integer>();
            int total = 0, u, v; //total은 간선의 갯수
            boolean isTree = true;
            while(0 <= caseN){
                u = sc.nextInt();
                v = sc.nextInt();
                if(u ==-1 && v == -1) { 
                // -1 -1이 들어오면 flag값을 바꾸어 탈출
                    flag = false;
                    break;
                }
                if(u == 0 && v == 0 ) {
                    // tree 판별
                    caseN++;
                    if(1 < root.size() || (total+1) != root.size() + children.size() )
                    // root가 2개 이상이거나, 간선의 갯수가 노드-1이 아닐 때 - 트리가 아님
                        isTree = false;
                    if( isTree || total== 0) 
                    // total = 0 은 노드가 아예 없는 트리 
                    sb.append("Case "+caseN + " is a tree.\n");
                    else sb.append("Case "+caseN + " is not a tree.\n");
                    break;
                }
                else if(isTree) { // 아직까지 n번째 트리가 트리임이 유효할 때
                    total++; //간선의 갯수를 늘림
                    if(!children.contains(u)) root.add(u); //root은 일단 넣고 누군가의 자식노드(들어오는 노드)가 될 때 뺀다.
                    if(children.contains(v)) isTree = false; // 해당 노드로 들어오는 간선이 두 개이상이 되었으므로 더이상 트리가 아니다.
                    else{
                        if(root.contains(v)) root.remove(v); // 이전에 root였다면 이제는 누군가의 자식노드가 되었으므로 root집합에서 제외한다.
                        children.add(v); //자식노드로 슝 넣어준다.
                    }
                }
            }
        }
        System.out.println(sb);
    }
}