1719. Number Of Ways To Reconstruct A Tree

You are given an array pairs, where pairs[i] = [xi, yi], and:

• There are no duplicates.
• xi < yi

Let ways be the number of rooted trees that satisfy the following conditions:

• The tree consists of nodes whose values appeared in pairs.
• A pair [xi, yi] exists in pairs if and only if xi is an ancestor of yi or yi is an ancestor of xi.
• Note: the tree does not have to be a binary tree.

Two ways are considered to be different if there is at least one node that has different parents in both ways.

Return:

• 0 if ways == 0
• 1 if ways == 1
• 2 if ways > 1

A rooted tree is a tree that has a single root node, and all edges are oriented to be outgoing from the root.

An ancestor of a node is any node on the path from the root to that node (excluding the node itself). The root has no ancestors.

class Solution {
public:
    int checkWays(vector<vector<int>>& pairs) {
        unordered_map<int, unordered_set<int>> adj;
        for(auto& pair : pairs) {
            int u = pair[0], v = pair[1];
            adj[u].insert(v);
            adj[v].insert(u);
        }

        priority_queue<pair<int, int>> pq;
        for(auto [u, adjs] : adj) {
            pq.push({adjs.size(), u});
        }
        bool multiroot = false;
        unordered_set<int> seen;
        while(!pq.empty()) {
            auto [sz, u] = pq.top(); pq.pop();
            auto par = -1, parsz = INT_MAX;
            if(seen.size()) {
                for(auto& v : adj[u]) {
                    if(seen.count(v) and parsz > adj[v].size()) {
                        par = v;
                        parsz = adj[v].size();
                    }
                }
            }

            seen.insert(u);
            if(par == -1 and sz != adj.size() - 1) return 0;

            if(par != -1) {
                for(auto& v : adj[u]) {
                    if(v == par) continue;
                    if(!adj[v].count(par)) return 0;
                }

                if(parsz == sz) multiroot = true;
            }
        }
        return multiroot ? 2 : 1;
    }
};