为啥错了呢
查看原帖
为啥错了呢
416959
alexbear103楼主2021/5/26 20:43
#include <bits/stdc++.h>
using namespace std;
const int maxn = 105;
const int maxm = 10005;
struct Edge {
    int v, next;
} edge[maxn];
int p[maxn], eid;
void init() {
    memset(p, -1, sizeof p);
}
void insert(int u, int v) {
    edge[eid++].v = v;
    edge[eid].next = p[u];
    p[u] = eid;
}
int n, u, v;
int dfn[maxn], low[maxn];
int timer;
bool vis[maxn];
void tarjan(int u, int father) {
    dfn[u] = low[u] = ++timer;
    int child = 0;
    for (int i = p[u]; i != -1; i = edge[i].next) {
        int v = edge[i].v;
        if (!dfn[v]) {
            child++;
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            //cout << low[v] << ' ' << dfn[u] << endl;
            if (u != father && low[v] >= dfn[u]) {
                //printf("%d %d %d %d\n", u, v, dfn[v], dfn[u]);
                vis[u] = true;
            }
        } else if (/*low[u] > dfn[v] &&*/ v != father) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (u == father && child == 1) {
        vis[u] = false;
    }
}
int main() {
    freopen("telecom.in", "r", stdin);
    freopen("telecom.out", "w", stdout);
    init();
    cin >> n;
    cin >> u;
    while (u) {
        cin >> v;
        insert(u, v);
        insert(v, u);
        cin >> u;
    }
    tarjan(1, 1);
    /*for (int i = 1; i <= n; ++i) {
        cout << low[i] << ' ';
    }
    cout << endl;
    for (int i = 1; i <= n; ++i) {
        cout << dfn[i] << ' ';
    }*/
    for (int i = 1; i <= n; ++i) {
        if (vis[i]) {
            cout << i << endl;
        }
    }
    return 0;
}
2021/5/26 20:43
加载中...