thảo luận Leetcode mỗi ngày

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        graph = defaultdict(list)
        for u, v in connections:
            graph[v].append((u, True))
            graph[u].append((v, False))
      
        count = 0
        def dfs(node, parent):
            nonlocal count
            for nei in graph[node]:
                child, sign = nei
                if child != parent:
                    count += (1-sign)
                    dfs(child, node)
        dfs(0, -1)
        return count

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        edges = defaultdict(list)
        for edge in connections:
            edges[edge[0]].append(edge)
            edges[edge[1]].append(edge)
        ret = 0
        visited = [False] * n
        nodes = [0]
        visited[0] = True
        while nodes:
            node = nodes.pop()
            for x, y in edges[node]:
                if node == x:
                    if not visited[y]:
                        ret += 1
                        nodes.append(y)
                        visited[y] = True
                else:
                    if not visited[x]:
                        nodes.append(x)
                        visited[x] = True
        return ret

class UnionFind:
    def __init__(self, n):
        self.ranks = [1 for _ in range(n)]
        self.roots = [i for i in range(n)]
    
    def union(self, x, y):
        root_x, root_y = self.find(x), self.find(y)
        if root_x != root_y:
            if self.ranks[root_x] > self.ranks[root_y]:
                self.roots[root_y] = root_x
            elif self.ranks[root_x] < self.ranks[root_y]:
                self.roots[root_x] = root_y
            else:
                self.roots[root_y] = root_x
                self.ranks[root_x] += 1
    
    def connected(self, x, y):
        return self.find(x) == self.find(y)
    
    def find(self, x):
        if x == self.roots[x]:
            return x
        self.roots[x] = self.find(self.roots[x])
        return self.roots[x]

class Solution:
    def countPairs(self, n: int, edges: List[List[int]]) -> int:
        uf = UnionFind(n)
        for a, b in edges:
            uf.union(a, b)
        
        from collections import defaultdict
        cnts = defaultdict(int)
        for i in range(n):
            cnts[uf.find(i)] += 1
        
        ks = list(cnts.keys())
        total_s = sum(cnts.values())
        s = 0
        for i in ks:
            s += (total_s - cnts[i])*cnts[i]
        return int(s//2)

class Solution:
    def countPairs(self, n: int, edges: List[List[int]]) -> int:
        self.adj = defaultdict(list)
       
        for a, b in edges:
            self.adj[a].append(b)
            self.adj[b].append(a)
           
        self.visited = set()
       
        res = 0
       
        for node in range(n):
            if node in self.visited:
                continue
               
            count = self.dfs(node)
            res += count * (n - len(self.visited))
           
        return res
   
    def dfs(self, node):
        if node in self.visited:
            return 0
       
        self.visited.add(node)
       
        count = 1
       
        for neigh in self.adj[node]:
            count += self.dfs(neigh)
           
        return count

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number}
 */
var countPairs = function(n, edges) {
    const nb = Array.from({ length: n }, () => []);
    const visited = Array.from({ length: n }).fill(false);
    let ans = 0;
    edges.forEach(([u, v]) => {
        (nb[u] ??= []).push(v);
        (nb[v] ??= []).push(u);
    });

    const dfs = (node) => {
        visited[node] = true;
        let cntr = 1;
        nb[node].forEach(child => {
            cntr += visited[child] ? 0 : dfs(child, node);
        });

        return cntr;
    };

    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            const t = dfs(i);
            ans += t * (n - t);
        }
    }

    return ans / 2;
};

class Solution {
    void combination(vector<int>& candidates, int target, vector<int> currComb, int currSum, int currIndex, vector<vector<int>>& ans){
        if(currSum>target) return; //backtrack
        if(currSum==target){
            ans.push_back(currComb); //store the solution and backtrack
            return;
        }
        
        for(int i=currIndex; i<candidates.size(); i++){ //try all possible options for the next level
            currComb.push_back(candidates[i]); //put 1 option into the combination
            currSum+=candidates[i];
            combination(candidates, target, currComb, currSum, i, ans); //try with this combination, whether it gives a solution or not.
            currComb.pop_back(); //when this option backtrack to here, remove this and go on to the next option.
            currSum-=candidates[i];
        }
        
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        vector<int> currComb;
        combination(candidates, target, currComb, 0, 0, ans);
        return ans;
    }
};

fun countPairsDFS(n: Int, edges: Array<IntArray>): Long {
    val graph: MutableMap<Int, MutableList<Int>> = mutableMapOf()
    for (i in 0 until n) graph[i] = mutableListOf()

    for (e in edges) {
        graph[e[0]]!!.add(e[1])
        graph[e[1]]!!.add(e[0])
    }

    var result: ULong = 0u
    val graphVisitedNodes = MutableList(n) { false }

    fun dfs(node: Int): Int {
        graphVisitedNodes[node] = true
        var cntr = 1
        graph[node]!!.forEach {
            cntr += if (graphVisitedNodes[it]) 0 else dfs(it)
        }

        return cntr
    }

    for (i in 0 until n) {
        if (graphVisitedNodes[i]) continue
        val c = dfs(i)
        result += (c.toULong() * (n.toULong() - c.toULong())).toULong()
    }

    return (result / 2u).toLong()
}

class Solution {
    
    class UnionFind {
        int[] root;
        
        public UnionFind(int size) {
            root = new int[size];
            
            for (int i = 0; i < size; i++) {
                root[i] = i;
            }
        }
        
        public int find(int x) {
            if (root[x] == x) {
                return x;
            }
            
            return root[x] = find(root[x]);
        }
        
        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            
            if (rootX != rootY ) {
                root[rootX] = rootY;
            }
        }
    }
    
    public long countPairs(int n, int[][] edges) {
        UnionFind uf = new UnionFind(n);
        
        for (int i = 0; i < edges.length; i++) {
            uf.union(edges[i][0], edges[i][1]);
        }
        
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int i = 0; i < n; i++){
            int root = uf.find(i);
            map.put(root, map.getOrDefault(root, 0) + 1);
        }
        
        long ans = 0;
        for (int root : map.keySet()) {
            ans += (long) (n - map.get(root)) * map.get(root);
        }
        
        return ans / 2;
    }
}

class Solution {
    public long countPairs(int n, int[][] edges) {
        DSU set = new DSU();
        for(int[] e : edges){
            set.union(e[0], e[1]);
        }
        HashMap<Integer, Integer> components = new HashMap<>();
        for(int i = 0; i < n; i++){
            int parent = set.find(i);
            components.put(parent, components.getOrDefault(parent, 0) + 1);
        }
        long ans = 0;
        long N = n;
        for(int numsOfNode : components.values()){
            ans += numsOfNode * (N - numsOfNode);
            N = N - numsOfNode;
        }
        return ans;
    }
}

class DSU {
    private HashMap<Integer, Integer> parent;
    private HashMap<Integer, Integer> size;

    public DSU(){
        this.parent = new HashMap<>();
        this.size = new HashMap<>();
    }
    public void create(int i){
        parent.put(i, i);
        size.put(i, 1);
    }
    public int find(int i){
        if(parent.get(i) == null){
            this.create(i);
            return i;
        }
        if(i == parent.get(i)){
            return i;
        }
        // Nén đường đi
        int tmp = find(parent.get(i));
        parent.put(i, tmp);
        return tmp;
    }
    public void union(int a, int b){
        int tmp1 = this.find(a);
        int tmp2 = this.find(b);
        // Gộp theo kích cỡ
        if(tmp1 != tmp2){
            if(size.get(tmp1) < size.get(tmp2)){
                int tmp = tmp1;
                tmp1 = tmp2;
                tmp2 = tmp;
            }
            this.parent.put(tmp2, tmp1);
            size.put(tmp1, size.get(tmp1) + size.get(tmp2));
        }
    }
}

function countPairs(n: number, edges: number[][]): number {
    const map: Map<number, number[]> = new Map();
    for (const [e0, e1] of edges) {
        if (map.has(e0)) {
            const val = map.get(e0);
            val.push(e1);
            map.set(e0, val)
        } else {
            map.set(e0, [e1])
        }
        if (map.has(e1)) {
            const val = map.get(e1);
            val.push(e0);
            map.set(e1, val)
        } else {
            map.set(e1, [e0])
        }
    }
    const bfs = (node: number) => {
        const queue: number[] = [];
        queue.push(node);
        let count = 1;
        visited[node] = true;
        while (queue.length) {
            const item = queue.shift();
            if (!map.has(item)) {
                continue;
            }
            for (const adj of map.get(item)) {
                if (!visited[adj]) {
                    visited[adj] = true;
                    count++;
                    queue.push(adj)
                }
            }
        }
        return count;
    }
    let ans = 0, sz = 0, rest = n;
    const visited = new Array(n).fill(false);
    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            sz = bfs(i);
            ans += sz * (rest - sz);
            rest -= sz;
        }
    }
    return ans;
};

func findRoot(parents []int, th int) int {
    for parents[th] != th {
        th = parents[th]
    }
    return th
}

func countPairs(n int, edges [][]int) int64 {
    var res int64 = 0
    parents := make([]int, n)
    parentLen := make([]int, n)

    for i := n-1; i >= 1; i-- {
        res = res + int64(i)
        parents[i] = i
        parentLen[i] = 1
    }

    parents[0] = 0
    parentLen[0] = 1

    for _, v := range edges {
        var (
            rv0 int = findRoot(parents, v[0])
            rv1 int = findRoot(parents, v[1])
        )

        if rv0 != rv1 {
            res = res - (int64(parentLen[rv1]) * int64(parentLen[rv0]))
        }

        if rv0 < rv1 {
            parents[rv1] = rv0
            parentLen[rv0] = parentLen[rv0] + parentLen[rv1]
        } else {
            parents[rv0] = rv1
            parentLen[rv1] = parentLen[rv1] + parentLen[rv0]
        }
    }

    return res
}

/**
 * @param {number[]} edges
 * @return {number}
 */
var longestCycle = function(edges) {
    const n = edges.length;
    let ans = -1;

    const go = node => {
        const steps = {};
        let cntr = 0;

        while (++cntr) {
            if (steps[node]) {
                ans = Math.max(ans, cntr - steps[node]);
                break;
            }

            steps[node] = cntr;

            if (edges[node] >= 0) {
                const next = edges[node];
                edges[node] = -1;
                node = next;
            } else {
                break;
            }
        }
    };

    for (let i = 0; i < n; i++) {
        if (edges[i] >= 0) {
            go(i);
        }
    }

    return ans;
};

class Solution:
    def longestCycle(self, edges: List[int]) -> int:
        from collections import defaultdict
        G = defaultdict(list)
        for i, v in enumerate(edges):
            G[i].append(v)

        def dfs(node, curr):
            nonlocal visited, stack, ans
            visited.add(node)
            stack[node] = curr
            for nei in G[node]:
                if nei not in visited:
                    dfs(nei, curr + 1)
                elif nei in stack:
                    ans = max(ans, curr + 1 - stack[nei])
            del stack[node]
            return


            
        visited = set()
        stack = {}
        ans = -1
        for node in range(len(edges)):
            if node not in visited:
                dfs(node, 0)
        return ans

function longestCycle(edges: number[]): number {
    const n = edges.length;
    let ans = -1;
    const visited = new Array(n).fill(false);

    const dfs = (node: number, map: Map<number, number>) => {
        visited[node] = true;
        const val = edges[node];
        if (val !== -1) {
            if (!visited[val]) {
                map.set(val, map.get(node) + 1);
                dfs(val, map)
            } else if (map.has(val)) {
                ans = Math.max(ans, map.get(node) - map.get(val) + 1)
            }
        }

    }

    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            const map: Map<number, number> = new Map();
            map.set(i, 1);
            dfs(i, map);
        }
    }
    return ans

};

class Solution {
    int ans = -1;
    public int longestCycle(int[] edges) {
        int[] map = new int[edges.length];
        for (int i = 0; i < edges.length; i++) {
            if (edges[i] >= 0) {
                helper(i, edges, map);
            }
        }       

        return this.ans;
    }

    void helper(int node, int[] edges, int[] map) {
        Map<Integer,Integer> cnts = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        int cnt = 1;
        stack.push(node);
        while(!stack.isEmpty()){
            int cur = stack.pop();
            
            if (map[cur] > 0) {
                for (int i : cnts.keySet()) {
                    map[i] = map[cur];
                }
                return;
            }

            if (cnts.getOrDefault(cur, 0) > 0) {
                int cycleLength = cnt - cnts.get(cur);
                this.ans = Math.max(this.ans, cycleLength);
                for (int i : cnts.keySet()) {
                    map[i] = cycleLength;
                }
                return;
            }

            if (edges[cur] >= 0) {
                stack.push(edges[cur]);
            }
            cnts.put(cur, cnt);
            cnt++;
        }
    }
}

class Solution:
    def longestCycle(self, edges: List[int]) -> int:
        self.visited = set()
        self.edges = edges
        n = len(edges)
        
        maxCycle = -1
        for node in range(n):
            if node in self.visited:
                continue
                
            maxCycle = max(maxCycle, self.findCycle(node))
            
        return maxCycle
    
    def findCycle(self, node):
        slow = node
        fast = node
        
        cycle = False
        visited = set()
        visited.add(slow)
        while self.edges[fast] != -1 and self.edges[self.edges[fast]] != -1:
            slow = self.edges[slow]
            fast = self.edges[self.edges[fast]]
            visited.add(slow)
            visited.add(fast)
            
            if slow in self.visited or fast in self.visited:
                break
            
            if slow == fast:
                cycle = True
                break
        
        if not cycle:
            for node in visited:
                self.visited.add(node)
                
            return -1
        
        slow = node
        while slow != fast:
            slow = self.edges[slow]
            fast = self.edges[fast]
            visited.add(fast)
            
        count = 1
        curr = self.edges[slow]
        while curr != slow:
            curr = self.edges[curr]
            count += 1
            
        for node in visited:
            self.visited.add(node)
            
        return count