找出直系親屬

題目

找出直系親屬

代碼和分析

import java.util.Arrays;
import java.util.Scanner;

/*
 * 題意上，類似樹，這裡左節點和右節點是根節點的雙親。
 * 用了並查集。
 * 這裡並查集的parent向量，記錄的仍是該點所在樹的父節點。
 * */

public class Main {
    private static int parent[];
    private static int n=0;
    private static int m=0;
    
    //預處理：每個點為一個樹，該點即為根子樹
    public static void preProcess(){
        for(int i=0;i<26;i++){
            parent[i]=i;
        }
    }
    
    //尋找x的後代y隔了幾代（即x的祖先節點是否有y）
    public static int getDisc(int x,int y){
        int distance=0;
    
        while(x!=y && parent[x]!=x){
            distance++;
            x=parent[x];
        }
        
        if(x==y) return distance;
        else return 0;
    }
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        while(scan.hasNext()){
            int n=scan.nextInt();
            int m=scan.nextInt();
            if(n==0 && m==0) break;
            
            parent=new int[26];
            preProcess();
            
            for(int i=0;i<n;i++){
                String str=scan.next();
                int child=str.charAt(0)-'A';
                if(str.charAt(1)!='-') parent[str.charAt(1)-'A']=child;;
                if(str.charAt(2)!='-') parent[str.charAt(2)-'A']=child;
            }
            for(int i=0;i<m;i++){
                String str=scan.next();
                int person1=str.charAt(0)-'A';
                int person2=str.charAt(1)-'A';
                
                int distance=getDisc(person1,person2);
                if(distance!=0){  //person1為長輩，person2為後代
                    
                    if(distance==1){
                        System.out.println("parent");
                    }else if(distance==2){
                        System.out.println("grandparent");
                    }else{
                        for(int k=2;k<distance;k++){
                            System.out.print("great-");
                        }
                        System.out.println("grandparent");
                    }
                    
                }else{            //person2為長輩，person1為後代
                    distance=getDisc(person2,person1);
                    
                    if(distance==0){
                        System.out.println("-");
                    }else if(distance==1){
                        System.out.println("child");
                    }else if(distance==2){
                        System.out.println("grandchild");
                    }else{
                        for(int k=2;k<distance;k++){
                            System.out.print("great-");
                        }
                        System.out.println("grandchild");
                    }
                    
                }
            }
        }
        
        
        scan.close();
    }
    
}