割点和桥

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int a, b;
struct Graph {
    int n, rt, tot, ccnt;
    vector<vector<int>> adj;
    vector<int> dfn, low;
    vector<bool> iscut;
    Graph(int n) : n(n), adj(n + 1), iscut(n + 1), dfn(n + 1), low(n + 1), tot(0), ccnt(0) { }
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    void tarjan(int u) {
        dfn[u] = low[u] = ++tot;
        int child = 0;
        for (auto &to : adj[u]) {
            if (!dfn[to]) {
                child++;
                tarjan(to);
                low[u] = min(low[u], low[to]);
                if (low[to] >= dfn[u]) {
                    if (u != rt && dfn[b] >= dfn[to]) {
                        iscut[u] = true;
                    }
                }
            } else {
                low[u] = min(low[u], dfn[to]);
            }
        }
    }
    void cutPoint() {
        rt = a;
        tarjan(a);
    }
}; // Graph
// 定义 Graph g(n) 表示一个 n 个点的无向图
// 使用 g.addEdge(u, v) 进行添加无向边 (u, v)
// 使用 g.cutPoint() 即可进行割点
int main() {
    int n;
    cin >> n;
    Graph g(n);
    int u, v;
    while (cin >> u >> v) {
        if (u == 0 && v == 0) break;
        g.addEdge(u, v);
    }
    cin >> a >> b;
    g.cutPoint();
    auto iscut = g.iscut;
    for (int i = 1 ; i <= n ; i++) {
        if (iscut[i]) {
            cout << i << "\n";
            return 0;
        }
    }
    cout << "No solution\n";
    return 0;
}

struct Graph {
    int n, tot, ccnt;
    vector<vector<int>> adj;
    vector<int> dfn, low, bridge;
    vector<array<int, 2>> edges;
    Graph(int n) : n(n), adj(n + 1), dfn(n + 1), low(n + 1), tot(0), ccnt(0) { }
    void addEdge(int u, int v) {
        adj[u].push_back(edges.size());
        edges.push_back({u, v});
        adj[v].push_back(edges.size());
        edges.push_back({v, u});
    }
    void tarjan(int u, int e) {
        dfn[u] = low[u] = ++tot;
        for (auto idx : adj[u]) {
            int to = edges[idx][1];
            if (!dfn[to]) {
                tarjan(to, idx);
                low[u] = min(low[u], low[to]);
                if (low[to] > dfn[u]) {
                    bridge.push_back(idx);
                }
            } else if (dfn[to] < dfn[u] && idx != (e ^ 1)) {
                low[u] = min(low[u], dfn[to]);
            }
        }
    }
    void cutEdge() {
        for (int i = 1 ; i <= n ; i++) {
            if (!dfn[i]) {
                tarjan(i, -1);
                ccnt++;
            }
        }
    }
}; // Graph
// 定义 Graph g(n) 表示一个 n 个点的无向图.
// 使用 g.addEdge(u, v) 进行添加无向边 (u, v).
// 使用 g.cutEdge() 即可进行割边.
// bridge 表示所有桥边的编号.

template<typename T>
struct Graph {
    struct Edge {
        int u, to;
        T val;
    };
    int n, tot, ccnt;
    vector<vector<int>> adj;
    vector<int> dfn, low, bridge;
    vector<Edge> edges;
    Graph(int n) : n(n), adj(n + 1), dfn(n + 1), low(n + 1), tot(0), ccnt(0) { }
    void addEdge(int u, int v, T val) {
        adj[u].push_back(edges.size());
        edges.push_back({u, v, val});
        adj[v].push_back(edges.size());
        edges.push_back({v, u, val});
    }
    void tarjan(int u, int e) {
        dfn[u] = low[u] = ++tot;
        for (auto idx : adj[u]) {
            int to = edges[idx].to;
            if (!dfn[to]) {
                tarjan(to, idx);
                low[u] = min(low[u], low[to]);
                if (low[to] > dfn[u]) {
                    bridge.push_back(idx);
                }
            } else if (dfn[to] < dfn[u] && idx != (e ^ 1)) {
                low[u] = min(low[u], dfn[to]);
            }
        }
    }
    void cutEdge() {
        for (int i = 1 ; i <= n ; i++) {
            if (!dfn[i]) {
                tarjan(i, -1);
                ccnt++;
            }
        }
    }
}; // Graph
// 定义 Graph<int> g(n) 表示一个 n 个点且权值在 int 范围内的无向图.
// 使用 g.addEdge(u, v, val) 进行添加无向边 (u, v) 权为 val.
// 使用 g.cutEdge() 即可进行割边.
// bridge 表示所有桥边的编号.