洛谷 P1656 炸铁路

思路

题目一眼 tarjan 求桥，属于模板题目。

代码

#include <bits/stdc++.h>
using namespace std;
int n, a[155][155];
int dfn[1005], l[1005], cnt, vis[1005];
//vector <int> ans;
int cntt;
int ans[155][155];

void dfs(int u, int fa) {
    dfn[u] = ++cnt;
    vis[u] = 1;
    l[u] = dfn[u];

    for (int v = 1; v <= n; v ++) {
        if (a[u][v] == 1) {
            //是子节点
            a[u][v] = a[v][u] = 0;

            if (!dfn[v]) {
                    // cntt ++;

                    // if (cntt == 2) {
                    //  ans[u][v] = 1;
                    // }
                dfs(v, u);
                l[u] = min(l[u], l[v]);

                if (dfn[u] < l[v]) {
                        ans[u][v] = 1;
                }
            } else if (dfn[v] < dfn[u] && v != fa) {
                l[u] = min(l[u], dfn[v]);
            }
        }
    }
}
int m;
int main() {
    cin >> n >> m;

    while (m --) {
        int x, y; cin >> x >> y;
        a[x][y] = 1;
        a[y][x] = 1;
    }

    dfs(1, 0);
    int cnttt = 0;

    for (int i = 1; i <= 150; i ++) {
        for (int j = 1; j <= 150; j ++) {
            if (ans[i][j]) cout << i << " " << j << "\n", cnttt ++;
        }
    } 

    if (cnttt == 0)
        cout << "safe";
}