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

class Solution {
public:
    int minScore(int n, vector<vector<int>>& roads) {
        bool visited[n + 1];
        memset(visited, false, sizeof(visited));
        vector<vector<pair<int, int>>> conn(n + 1);
        for(vector<int>& edge : roads){
            conn[edge[0]].emplace_back(edge[1], edge[2]);
            conn[edge[1]].emplace_back(edge[0], edge[2]);
        }
        int res = 10'000;
        queue<tuple<int, int>> q;
        q.emplace(1, res);
        visited[1] = true;
        while(!q.empty()){
            auto [p, v] = q.front();
            for(pair<int, int>& c : conn[p]){
                res = min(res, min(v, c.second));
                if(!visited[c.first]){
                    q.emplace(c.first, res);
                    visited[c.first] = true;
                }
            }
            q.pop();
        }
        return res;
    }
};

class Solution {
public:
    int find(int *parent, int i){
        if(parent[i] == i) return i;
        return find(parent, parent[i]);
    }
    tuple<int, int> join(int *parent, int i, int j){
        int x = find(parent, i);
        int y = find(parent, j);
        if(x > y) swap(x, y);
        parent[y] = x;
        return {x, y};
    }
    int minScore(int n, vector<vector<int>>& roads) {
        int parent[n + 1], cost[n + 1];
        for(int i = 1; i <= n; ++i) cost[i] = INT_MAX, parent[i] = i;
        for(auto &ed : roads){
            auto [x, y] = join(parent, ed[0], ed[1]);
            cost[x] = min(min(cost[x], cost[y]), ed[2]);
        }
        return cost[1];
    }
};

fun minScore(n: Int, roads: Array<IntArray>): Int {
    val map: MutableMap<Int, MutableMap<Int, Int>> = mutableMapOf()

    for (r in roads) {
        val city1 = r[0]
        val city2 = r[1]
        val distance = r[2]
        val result1 = map.getOrElse(city1) {
            mutableMapOf(city2 to distance).also { map[city1] = it }
        }
        result1.computeIfAbsent(city2) { distance }
        val result2 = map.getOrElse(city2) {
            mutableMapOf(city1 to distance).also { map[city2] = it }
        }
        result2.computeIfAbsent(city1) { distance }
    }

    var minScore: Int = Int.MAX_VALUE
    val passedCities: MutableMap<Int, MutableMap<Int, Boolean>> = mutableMapOf()

    fun traversal(start: Int, cities: Map<Int, Int>) {
        for (entry in cities) {
            if (passedCities[start]?.get(entry.key) == null) {
                minScore = entry.value.coerceAtMost(minScore)
                val result1 = passedCities.getOrElse(start) {
                    mutableMapOf(entry.key to true).also { passedCities[start] = it }
                }
                result1.computeIfAbsent(entry.key) { true }
                val result2 = passedCities.getOrElse(entry.key) {
                    mutableMapOf(start to true).also { passedCities[entry.key] = it }
                }
                result2.computeIfAbsent(entry.key) { true }
                traversal(entry.key, map[entry.key]!!)
            }
        }
    }

    traversal(1, map[1]!!)

    return minScore
}

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        self.adj = defaultdict(list)
        
        for a, b in connections:
            self.adj[a].append(b)
            self.adj[b].append(a)
            
        self.visited = [False] * n
        
        connected = 0
        minRequired = 0
        for node in range(0, n):
            if self.visited[node]:
                continue
            
            connected += 1
            count = self.dfs(node)
            minRequired += count - 1
            
        return connected - 1 if (len(connections) - minRequired) >= (connected - 1) else -1
    
    def dfs(self, node):
        if self.visited[node]:
            return 0
        
        self.visited[node] = True
        count = 1
        for neigh in self.adj[node]:
            count += self.dfs(neigh)
            
        return count

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 int makeConnected(int n, int[][] connections) {
        if (connections.length < n - 1) return -1;
        
        UnionFind uf = new UnionFind(n);
        int ans = n;
        for (int[] con : connections) {
            if (uf.find(con[0]) == uf.find(con[1])) continue;
            uf.union(con[0], con[1]);
            ans--;
        }
        
        return ans - 1;
    }
}

/**
 * @param {number} n
 * @param {number[][]} connections
 * @return {number}
 */
var makeConnected = function(n, connections) {
    if (connections.length < n-1) {
        return -1;
    }

    const p = Array(n).fill().map((_, idx) => idx);
    const pp = i => (p[i] === i ? i : p[i] = pp(p[i]));

    for (const [a, b] of connections) {
        p[pp(b)] = p[pp(a)];
    }

    p.forEach((v, i) => pp(i));

    return _.uniq(p).length - 1;
};

function makeConnected(n: number, connections: number[][]): number {
    if (connections.length < n - 1) {
        return -1;
    }
    const map: Map<number, number[]> = new Map();
    const visited = new Array(n).fill(false);
    for (const [first, second] of connections) {
        if (map.has(first)) {
            const value = map.get(first);
            value.push(second);
            map.set(first, value)
        } else {
            map.set(first, [second])
        }

        if (map.has(second)) {
            const value = map.get(second);
            value.push(first);
            map.set(second, value)
        } else {
            map.set(second, [first])
        }
    }
    const bfs = (i: number) => {
        const queue: number[] = [];
        queue.push(i);
        visited[i] = true;
        while (queue.length) {
            const item = queue.shift();
            if (!map.get(item)) return;
            for (const val of map.get(item)) {
                if (!visited[val]) {
                    visited[val] = true;
                    queue.push(val);
                }
            }
        }
    }
    let ans = 0;
    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            ans++;
            bfs(i)
        }
    }
    return ans - 1;
};

class Solution {
private:
    int find(int *parent, int i){
        if(parent[i] == i) return i;
        return find(parent, parent[i]);
    }
    void join(int *parent, int i, int j, int &n){
        int x = find(parent, i);
        int y = find(parent, j);
        n -= x != y;
        if(x < y) swap(x, y); // trick to speed up
        parent[x] = y;
    }
public:
    int makeConnected(int n, vector<vector<int>>& connections) {
        if(connections.size() < n - 1) return -1;
        int parent[n];
        iota(parent, parent + n, 0);
        for(auto &ed : connections)
            join(parent, ed[0], ed[1], n);
        return n - 1;
    }
};

fun makeConnected(n: Int, connections: Array<IntArray>): Int {
    val map: MutableMap<Int, MutableList<Int>> = mutableMapOf()

    for (i in 0 until n) {
        map[i] = mutableListOf()
    }

    for (c in connections) {
        map[c[0]]!!.add(c[1])
        map[c[1]]!!.add(c[0])
    }

    var availableCableCount = 0
    for (entry in map) {
        availableCableCount += entry.value.fold(0) { acc, i ->
            if (i < entry.key) acc
            else acc + 1
        }
    }

    if (availableCableCount < n - 1) return -1

    var neededTimes = 0
    val notPassedComputers = MutableList(n) { it }

    fun traversal(node: Int) {
        if (notPassedComputers.contains(node)) {
            notPassedComputers.remove(node)
            for (c in map[node]!!) {
                traversal(c)
            }
        }
    }

    while (notPassedComputers.isNotEmpty()) {
        val node = notPassedComputers.first()
        neededTimes++
        traversal(node)
    }

    return neededTimes - 1
}

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        self.adj = defaultdict(list)
        self.reversed = defaultdict(set)
        
        for a, b in connections:
            self.adj[a].append(b)
            self.adj[b].append(a)
            self.reversed[a].add(b)
            
        self.visited = set()
        self.res = 0
        
        self.dfs(0)
        return self.res
    
    def dfs(self, node):
        if node in self.visited:
            return
        
        self.visited.add(node)
        
        count = 0
        for neigh in self.adj[node]:
            if neigh in self.reversed[node] and neigh not in self.visited:
                self.res += 1
                
            self.dfs(neigh)

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        
        def dfs(node):
            nonlocal edges,visited, G
            for nei in G[node]:
                if nei not in visited:
                    visited.add(nei)
                    edges.append((nei, node))
                    dfs(nei)

        from collections import defaultdict
        G = defaultdict(list)
        connections_2 = set()
        for a, b in connections:
            G[a].append(b)
            G[b].append(a)
            connections_2.add((a, b))
        edges = []
        visited = {0}
        dfs(0)

        ans = 0
        for edge in edges:
            if edge not in connections_2:
                ans += 1
        return ans

function minReorder(n: number, connections: number[][]): number {
    const map: Map<number, number[][]> = new Map();
    let ans = 0;
    for (const [first, second] of connections) {
        if (map.has(first)) {
            const value = map.get(first);
            value.push([second, 1]);
            map.set(first, value);
        } else {
            map.set(first, [[second, 1]])
        }

        if (map.has(second)) {
            const value = map.get(second);
            value.push([first, 0]);
            map.set(second, value);
        } else {
            map.set(second, [[first, 0]])
        }
    }

    const bfs = (node: number) => {
        const queue: number[] = [];
        const visited = new Array(n).fill(false);
        queue.push(node);
        visited[node] = true;
        while (queue.length > 0) {
            const item = queue.shift();
            if (!map.get(item)) continue;
            for (const [adj, dir] of map.get(item)) {
                if (!visited[adj]) {
                    ans += dir;
                    visited[adj] = true;
                    queue.push(adj);
                }
            }
        }
    }

    bfs(0)
    return ans;
};

/**
 * @param {number} n
 * @param {number[][]} connections
 * @return {number}
 */
var minReorder = function(n, connections) {
    const ins = [], outs = [];
    let ans = 0;

    connections.forEach(([u, v]) => {
        ins[v] ??= [];
        ins[v].push(u);
        outs[u] ??= [];
        outs[u].push(v);
    });

    const dfs = (node, parent) => {
        ins[node]?.forEach(it => it !== parent && dfs(it, node));
        outs[node]?.forEach(it => it !== parent && ++ans && dfs(it, node));
    };

    dfs(0);

    return ans;
}

class Solution {
    public int minReorder(int n, int[][] connections) {
        int[] levels = new int[n];
        Map<Integer, List<Integer>> map = new HashMap<>();
        boolean[] visited = new boolean[n];

        for (int[] con : connections){
            map.computeIfAbsent(con[0], (x) -> new ArrayList<>());
            map.computeIfAbsent(con[1], (x) -> new ArrayList<>());
            map.get(con[0]).add(con[1]);
            map.get(con[1]).add(con[0]);
        }

        Queue<Integer> q = new LinkedList<>();
        q.add(0);
        visited[0] = true;
        int level = 0;
        while(!q.isEmpty()){
            int size = q.size();
            for (int i = 0; i < size; i++){
                int cur = q.poll();
                for (int nb : map.get(cur)){
                    if (visited[nb]) continue;
                    visited[nb] = true;
                    q.add(nb);
                }
                levels[cur] = level;
            }
            level++;
        }

        int ans = 0;
        for (int[] con : connections) {
            int src = con[0];
            int dest = con[1];
            if (levels[src] < levels[dest]) ans++;
        }

        return ans;
    }
}

func minReorder(n int, connections [][]int) int {
    m := make(map[int][]int)
    st := make(map[string]bool)
    for _, v := range connections {
        str := strconv.Itoa(v[0]) + "," + strconv.Itoa(v[1])
        st[str] = true
        m[v[0]] = append(m[v[0]], v[1])
        m[v[1]] = append(m[v[1]], v[0])
    }
    visited := make(map[int]bool)
    var count int
    dfs(0, m, visited, st, &count)
    return count
}
func dfs(node int, m map[int][]int, visited map[int]bool, st map[string]bool, count *int) {
    visited[node] = true
    for _, v := range m[node] {
        if !visited[v] {
            str := strconv.Itoa(node) + "," + strconv.Itoa(v)
            if st[str] {
                *count++
            }
            dfs(v, m, visited, st, count)
        }
    }
}