【leetcode】1719. Number of schemes for reconstructing a tree

subject ：
1719. The number of schemes to reconstruct a tree
Give you an array pairs , among pairs[i] = [xi, yi] , And satisfy ：
pairs There is no repeating element
xi < yi
Make ways The number of schemes with roots satisfying the following conditions ：

All node values contained in the tree are in pairs in .
A couple [xi, yi] Appear in the pairs in If and only if xi yes yi Ancestors or yi yes xi The ancestors of the .
Be careful ： The constructed tree is not necessarily a binary tree .
Two trees are treated as different schemes when there is at least one node and there are different parent nodes in the two trees .
Please return ：
If ways == 0 , return 0 .
If ways == 1 , return 1 .
If ways > 1 , return 2 .
A tree Rooting tree It refers to a tree with only one root node , All edges are from the root to the outside .

We call any node on the path from the root to a node （ Remove the node itself ） Are all of this node The ancestors . The root node has no ancestors .

Example 1：

Input ：pairs = [[1,2],[2,3]]
Output ：1
explain ： As shown in the figure above , There is and only one qualified rooted tree .
Example 2：

Input ：pairs = [[1,2],[2,3],[1,3]]
Output ：2
explain ： There are multiple qualified rooted trees , Three of them are shown in the figure above .

Example 3：
Input ：pairs = [[1,2],[2,3],[2,4],[1,5]]
Output ：0
explain ： There is no root tree that meets the regulations .

Tips ：

1 <= pairs.length <= 105
1 <= xi < yi <= 500
pairs The elements in are different from each other .

class Solution {
    
    public int checkWays(int[][] pairs) {
    
        Set<Integer>[] path=new Set[505];// Record which other points each point has a grandson relationship with 
        for(int i=0;i<path.length;i++){
    path[i]=new HashSet<>();}
        int numOfNodes=0;
        int mostRelations=0;
        for(int i=0;i<pairs.length;i++){
    
            if(path[pairs[i][0]].size()==0){
    numOfNodes++;}
            if(path[pairs[i][1]].size()==0){
    numOfNodes++;}
            path[pairs[i][0]].add(pairs[i][1]);
            path[pairs[i][1]].add(pairs[i][0]);
            mostRelations=Math.max(mostRelations,Math.max(path[pairs[i][0]].size(),path[pairs[i][1]].size()));
        }
        if(numOfNodes!=mostRelations+1){
    return 0;}
        int rootVal=-1;// Total root nodes 
        int ans=1;
        for(int i=1;;i++){
    
            if(path[i].size()==mostRelations){
    
                rootVal=i;
                break;
            }
        }
        for(int p:path[rootVal]){
    
            //p yes root A descendant of , Let's start looking for p Parent node 
            int dad=-1,partnerNum=505;
            for(int partner:path[p]){
    
                if(rootVal==p){
    continue;}
                if(partnerNum>path[partner].size()&&path[partner].size()>=path[p].size()){
    
                    dad=partner;
                    partnerNum=path[partner].size();
                }
            }
            if(partnerNum==path[p].size()){
    ans=2;}
            for(int a:path[p]){
    
                if(a==dad){
    continue;}
                if(!path[dad].contains(a)){
    return 0;}
            }
        }
        return ans;
    }
}