classic disjoint det
Intuition\nThis question can be solved by a classic Disjoint Set data structure.\n\n# Approach\nFor each request just check if all restrictions are not violated
# Intuition\nThis question can be solved by a classic [Disjoint Set](https://en.wikipedia.org/wiki/Disjoint-set_data_structure) data structure.\n\n# Approach\nFor each request just check if all restrictions are not violated.\n\n# Complexity\n- Time complexity:\n$$O(n\\times k\\times\\alpha(n))$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\n#[derive(Debug)]\nstruct DSet{\n    size: Vec<usize>,\n    parent: Vec<usize>,\n}\n\nimpl DSet{\n    fn new(n: usize)->Self{\n        Self{size: vec![1; n], parent: vec![n; n]}\n    }\n\n    fn set(&self, mut a: usize)->usize{\n        while self.parent[a]<self.parent.len(){\n            a=self.parent[a];\n        }\n        a\n    }\n\n    fn uni(&mut self, mut a: usize, mut b: usize){\n        (a, b)=(self.set(a), self.set(b));\n        if a!=b{\n            if self.size[a]<self.size[b]{(a, b)=(b, a);}\n            self.parent[b]=a;\n            self.size[a]+=self.size[b];\n        }\n    }\n\n    fn force_uni(&mut self, mut a: usize, mut b: usize){\n        if self.size[a]<self.size[b]{(a, b)=(b, a);}\n        self.parent[b]=a;\n        self.size[a]+=self.size[b];\n    }\n}\n\nimpl Solution {\n    pub fn friend_requests(n: i32, restrictions: Vec<Vec<i32>>, requests: Vec<Vec<i32>>) -> Vec<bool> {\n        let mut ds=DSet::new(n as usize);\n        let restrictions:Vec<_>=restrictions.into_iter().map(|r|(r[0] as usize, r[1] as usize)).collect();\n\n        let mut result=Vec::new();\n        \'out: for req in &requests{\n            let (mut a, mut b)=(ds.set(req[0] as usize), ds.set(req[1] as usize));\n            if a==b{\n                result.push(true);\n            }else{\n                if a>b{(a, b)=(b, a);}\n                for res in &restrictions{\n                    let (mut c, mut d)=(ds.set(res.0), ds.set(res.1));\n                    if c>d{(c, d)=(d, c);}\n                    if a==c&&b==d{\n                        result.push(false);\n                        continue \'out;\n                    }\n                }\n                result.push(true);\n                ds.force_uni(a, b);\n            }\n        }\n        result\n    }\n}\n```
['Union Find', 'Rust']