题目链接

题目大意

??给定多张无向图，求出每张图中割点数量。

解题思路

??模板题。

代码

const int maxn = 1e2+10;
vector<int> e[maxn];
int low[maxn], dfn[maxn], dn;
bool iscut[maxn];
void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++dn;
    int chd = 0;
    for (int i = 0; i<e[u].size(); ++i) {
        int v = e[u][i];
        if (!dfn[v]) {
            ++chd;
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v]>=dfn[u]&&u!=1) iscut[u] = true;
        }
        else if (low[v]<dfn[u]&& v!=fa)
            low[u] = min(low[u], dfn[v]);
    }
    if (u==1 && chd>=2) iscut[1] = true;
}
int main() {
    int n;
    while(cin>>n&&n) {
        getchar();
        string s;
        while(getline(cin, s)) {
            if (s=="0") break;
            stringstream ss; ss << s;
            int u, v; ss >> u;
            while(ss>>v) {
                e[u].push_back(v);
                e[v].push_back(u);
            }
        }
        tarjan(1, -1);
        int ans = 0;
        for (int i = 1; i<=n; ++i) {
            ans += iscut[i];
            e[i].clear();
        }
        cout << ans << endl;
        zero(low), zero(dfn), zero(iscut); dn = 0;
    }
    return 0;
}

POJ 1144 Network(tarjan求割点)

原文：https://www.cnblogs.com/shuitiangong/p/12884156.html