图连通性与并查集

from collections import deque


def is_bipartite(graph: list[list[int]]) -> bool:
    """Can the nodes be 2-coloured so every edge joins different colours? (LC 785)"""
    color = [-1] * len(graph)
    for s in range(len(graph)):  # every component, not only the one holding node 0
        if color[s] != -1:
            continue
        color[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v in graph[u]:
                if color[v] == -1:
                    color[v] = color[u] ^ 1  # the other colour
                    q.append(v)
                elif color[v] == color[u]:
                    return False  # an odd cycle
    return True

// Can the nodes be 2-coloured so every edge joins different colours? (LC 785)
bool isBipartite(const vector<vector<int>>& graph) {
    vector<int> color(graph.size(), -1);
    for (int s = 0; s < (int)graph.size(); s++) {  // every component, not only the one holding node 0
        if (color[s] != -1) continue;
        color[s] = 0;
        queue<int> q;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v : graph[u]) {
                if (color[v] == -1) {
                    color[v] = color[u] ^ 1;  // the other colour
                    q.push(v);
                } else if (color[v] == color[u]) {
                    return false;  // an odd cycle
                }
            }
        }
    }
    return true;
}

class Solution {
    // Can the nodes be 2-coloured so every edge joins different colours? (LC 785)
    boolean isBipartite(int[][] graph) {
        int[] color = new int[graph.length];
        Arrays.fill(color, -1);
        for (int s = 0; s < graph.length; s++) { // every component, not only the one holding node 0
            if (color[s] != -1) continue;
            color[s] = 0;
            Deque<Integer> q = new ArrayDeque<>(List.of(s));
            while (!q.isEmpty()) {
                int u = q.poll();
                for (int v : graph[u]) {
                    if (color[v] == -1) {
                        color[v] = color[u] ^ 1; // the other colour
                        q.offer(v);
                    } else if (color[v] == color[u]) {
                        return false; // an odd cycle
                    }
                }
            }
        }
        return true;
    }
}

// isBipartite reports whether the nodes can be 2-coloured so every edge joins different colours.
func isBipartite(graph [][]int) bool {
	color := make([]int, len(graph))
	for i := range color {
		color[i] = -1
	}
	for s := range graph { // every component, not only the one holding node 0
		if color[s] != -1 {
			continue
		}
		color[s] = 0
		q := []int{s}
		for len(q) > 0 {
			u := q[0]
			q = q[1:]
			for _, v := range graph[u] {
				if color[v] == -1 {
					color[v] = color[u] ^ 1 // the other colour
					q = append(q, v)
				} else if color[v] == color[u] {
					return false // an odd cycle
				}
			}
		}
	}
	return true
}

def critical_connections(n: int, connections: list[list[int]]) -> list[list[int]]:
    """Every bridge, an edge whose removal disconnects the graph (LC 1192)."""
    graph = [[] for _ in range(n)]
    for u, v in connections:
        graph[u].append(v)
        graph[v].append(u)
    disc = [0] * n  # discovery time; 0 = not visited yet
    low = [0] * n  # earliest discovery time the subtree reaches with one back edge
    timer = 1
    res = []

    def dfs(u: int, parent: int) -> None:
        nonlocal timer
        disc[u] = low[u] = timer
        timer += 1
        for v in graph[u]:
            if v == parent:
                continue  # assumes no parallel edges
            if disc[v]:
                low[u] = min(low[u], disc[v])  # a back edge
            else:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:  # v's subtree cannot climb above u without this edge
                    res.append([u, v])

    for s in range(n):
        if not disc[s]:
            dfs(s, -1)
    return res

// Every bridge, an edge whose removal disconnects the graph (LC 1192).
vector<pair<int, int>> criticalConnections(int n, const vector<pair<int, int>>& connections) {
    vector<vector<int>> graph(n);
    for (auto [u, v] : connections) {
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    vector<int> disc(n, 0), low(n, 0);  // disc 0 = not visited; low: earliest time reached with one back edge
    int timer = 1;
    vector<pair<int, int>> res;
    function<void(int, int)> dfs = [&](int u, int parent) {
        disc[u] = low[u] = timer++;
        for (int v : graph[u]) {
            if (v == parent) continue;  // assumes no parallel edges
            if (disc[v]) {
                low[u] = min(low[u], disc[v]);  // a back edge
            } else {
                dfs(v, u);
                low[u] = min(low[u], low[v]);
                if (low[v] > disc[u]) res.push_back({u, v});  // v's subtree cannot climb above u without this edge
            }
        }
    };
    for (int s = 0; s < n; s++)
        if (!disc[s]) dfs(s, -1);
    return res;
}

class Solution {
    private List<List<Integer>> graph;
    private int[] disc, low; // disc 0 = not visited; low: earliest time reached with one back edge
    private int timer;
    private List<int[]> res;

    // Every bridge, an edge whose removal disconnects the graph (LC 1192).
    List<int[]> criticalConnections(int n, int[][] connections) {
        graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] e : connections) {
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
        }
        disc = new int[n];
        low = new int[n];
        timer = 1;
        res = new ArrayList<>();
        for (int s = 0; s < n; s++)
            if (disc[s] == 0) dfs(s, -1);
        return res;
    }

    private void dfs(int u, int parent) {
        disc[u] = low[u] = timer++;
        for (int v : graph.get(u)) {
            if (v == parent) continue; // assumes no parallel edges
            if (disc[v] != 0) {
                low[u] = Math.min(low[u], disc[v]); // a back edge
            } else {
                dfs(v, u);
                low[u] = Math.min(low[u], low[v]);
                if (low[v] > disc[u]) res.add(new int[] {u, v}); // v's subtree cannot climb above u without this edge
            }
        }
    }
}

// criticalConnections returns every bridge, an edge whose removal disconnects the graph (LC 1192).
func criticalConnections(n int, connections [][2]int) [][2]int {
	graph := make([][]int, n)
	for _, e := range connections {
		graph[e[0]] = append(graph[e[0]], e[1])
		graph[e[1]] = append(graph[e[1]], e[0])
	}
	disc, low := make([]int, n), make([]int, n) // disc 0 = not visited; low: earliest time reached with one back edge
	timer := 1
	var res [][2]int
	var dfs func(u, parent int)
	dfs = func(u, parent int) {
		disc[u], low[u] = timer, timer
		timer++
		for _, v := range graph[u] {
			if v == parent {
				continue // assumes no parallel edges
			}
			if disc[v] != 0 {
				low[u] = min(low[u], disc[v]) // a back edge
			} else {
				dfs(v, u)
				low[u] = min(low[u], low[v])
				if low[v] > disc[u] { // v's subtree cannot climb above u without this edge
					res = append(res, [2]int{u, v})
				}
			}
		}
	}
	for s := 0; s < n; s++ {
		if disc[s] == 0 {
			dfs(s, -1)
		}
	}
	return res
}