边双连通分量 100pts 求调
查看原帖
边双连通分量 100pts 求调
589916
August_Light楼主2023/4/5 17:12

样例没过。

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> pii;
const int MAXN = 150 + 100;
const int MAXM = 1e4 + 100;
#define debug(x) fprintf(stderr, ""#x"\t= %d\n", x)
#define endOfDebug() fprintf(stderr, "---------\n")
struct Edge {
    int to, nxt;
};
struct Graph {
    int head[MAXN], cnt;
    Edge e[MAXM];
    void init() {
        memset(head, 0, sizeof(head));
        memset(e, 0, sizeof(e));
        cnt = 0;
    }
    void addedge(int u, int v) {
        e[cnt].to = v;
        e[cnt].nxt = head[u];
        head[u] = cnt;
        cnt++;
    }
};
Graph g;
namespace Tarjan {
    int dfn[MAXN], low[MAXN], bel[MAXN];
    stack<int> st;
    int cnt; // dfs 序
    vector<pii> edge; // 割边
    int idx; // 边双连通分量编号
    void dfs(int u, int lst) {
        low[u] = dfn[u] = ++cnt;
        st.push(u);
        for (int i = g.head[u]; i; i = g.e[i].nxt) {
            if (i == (lst ^ 1)) // 反边
                continue;
            int v = g.e[i].to;
            if (!dfn[v]) {
                dfs(v, i);
                low[u] = min(low[u], low[v]);
                if (low[v] > dfn[u])
                    edge.push_back(make_pair(min(u, v), max(u, v)));
            } else
                low[u] = min(low[u], dfn[v]);
        }
        if (low[u] == dfn[u]) {
            int v; idx++;
            do {
                v = st.top(); st.pop();
                bel[v] = idx;
            } while (v != u);
        }
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        g.addedge(a, b);
        g.addedge(b, a);
    }
    for (int i = 1; i <= n; i++)
        if (!Tarjan::dfn[i])
            Tarjan::dfs(i, -1);
    sort(Tarjan::edge.begin(), Tarjan::edge.end());
    for (pii e : Tarjan::edge)
        cout << e.first << ' ' << e.second << endl;
    return 0;
}
2023/4/5 17:12
加载中...