💥Beats 100% on runtime [EXPLAINED]
Intuition\nDetermine if two people can be friends based on a list of restrictions, where some pairs of people cannot be friends due to prior conditions. The key
# Intuition\nDetermine if two people can be friends based on a list of restrictions, where some pairs of people cannot be friends due to prior conditions. The key insight is that if two people belong to the same restricted pair, they cannot be friends, so we need to manage relationships dynamically while respecting these restrictions.\n\n# Approach\nUse a Disjoint Set Union (DSU) to group friends and check requests; for each request, temporarily union the two people, then verify against restrictions, restoring the state if invalid.\n\n# Complexity\n- Time complexity:\nO((R+Q)\u22C5\u03B1(N)), where \uD835\uDC45 R is the number of restrictions, \uD835\uDC44 Q is the number of requests, \uD835\uDC41 N is the number of people, and \uD835\uDEFC \u03B1 is the inverse Ackermann function, which grows very slowly, making this efficient in practice.\n\n- Space complexity:\nO(N) due to the storage of the parent and rank arrays in the DSU.\n\n# Code\n```csharp []\nusing System;\nusing System.Collections.Generic;\n\npublic class DSU\n{\n    public List<int> parent;\n    public List<int> rank;\n\n    public DSU(int n)\n    {\n        parent = new List<int>(new int[n]);\n        rank = new List<int>(new int[n]);\n\n        for (int i = 0; i < n; i++)\n        {\n            parent[i] = -1; // Initialize each node as its own parent\n            rank[i] = 0;    // Initialize rank to 0\n        }\n    }\n\n    public int Find(int i)\n    {\n        if (parent[i] == -1)\n        {\n            return i; // If it\'s its own parent, return itself\n        }\n        return parent[i] = Find(parent[i]); // Path compression\n    }\n\n    public void Union(int a, int b)\n    {\n        int s1 = Find(a);\n        int s2 = Find(b);\n\n        if (s1 != s2) // If they are not already in the same set\n        {\n            // Union by rank\n            if (rank[s1] >= rank[s2])\n            {\n                parent[s2] = s1; // Make s1 the parent of s2\n                rank[s1] += rank[s2]; // Update the rank of s1\n            }\n            else\n            {\n                parent[s1] = s2; // Make s2 the parent of s1\n                rank[s2] += rank[s1]; // Update the rank of s2\n            }\n        }\n    }\n}\n\npublic class Solution\n{\n    public bool[] FriendRequests(int n, IList<IList<int>> restrictions, IList<IList<int>> requests)\n    {\n        DSU dsu = new DSU(n); // Create an instance of DSU\n        List<bool> ans = new List<bool>(); // To store the result of each request\n        \n        // Process each friend request\n        foreach (var request in requests)\n        {\n            int u = request[0];\n            int v = request[1];\n            bool canBeFriends = true;\n\n            // Backup the current state of the DSU\n            var backupParent = new int[n];\n            var backupRank = new int[n];\n            Array.Copy(dsu.parent.ToArray(), backupParent, n);\n            Array.Copy(dsu.rank.ToArray(), backupRank, n);\n            \n            dsu.Union(u, v); // Temporarily union the friends\n            \n            // Check all restrictions\n            foreach (var restriction in restrictions)\n            {\n                // If both people in the restriction are in the same connected component\n                if (dsu.Find(restriction[0]) == dsu.Find(restriction[1]))\n                {\n                    canBeFriends = false; // They cannot be friends due to restriction\n                    break;\n                }\n            }\n\n            if (canBeFriends)\n            {\n                ans.Add(true); // If no restrictions were violated, the request is successful\n            }\n            else\n            {\n                ans.Add(false); // If restrictions were violated, reject the request\n                // Restore the backup if the request is rejected\n                dsu.parent = new List<int>(backupParent);\n                dsu.rank = new List<int>(backupRank);\n            }\n        }\n\n        return ans.ToArray(); // Convert List<bool> to bool[] and return\n    }\n}\n\n```
['Union Find', 'Graph', 'C#']