HDU 3394 Railway（桥+点双）

题目链接

题意

给你一副无向图，求桥数量 和 属于多个环的边数量

思路

求桥好写，属于多个环的边数，仙人掌判断恰好这么处理，求点双，点双内的边数大于点数则点双内每条边属于多个环。

代码

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int N = 10005;
vector<int> e[N], ds[N];
int ans1, ds_cnt, ans2;
int low[N], dfn[N], tot, vis[N];
stack<int> st;

void tarjan(int u, int fa) {
    low[u] = dfn[u] = ++tot;
    st.push(u);
    for(auto v : e[u]) {
        if(v == fa) continue;
        if(!dfn[v]) {
            tarjan(v,u), low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u]) {
                if(low[v] > dfn[u]) ++ans1;
                ++ds_cnt;
                while(1) {
                    int now = st.top();
                    st.pop();
                    ds[ds_cnt].push_back(now);
                    if(now == v) break;
                }
                ds[ds_cnt].push_back(u);
            }
        }
        else low[u] = min(low[u], dfn[v]);
    }
}

int main() {
    int n, m;
    while(~scanf("%d%d",&n,&m), n+m) {
        ans1 = ds_cnt = ans2 = 0;
        for(int i = 0; i <= n; ++i) e[i].clear(), dfn[i] = low[i] = 0, ds[i].clear();
        while(m--) {
            int u, v;
            scanf("%d%d",&u,&v);
            e[u].push_back(v);
            e[v].push_back(u);
        }
        for(int i = 0; i < n; ++i) if(!dfn[i]) tarjan(i,i);
        for(int i = 1; i <= ds_cnt; ++i) {
            int cnt = 0;
            for(auto u : ds[i]) vis[u] = 1;
            for(auto u : ds[i]) {
                for(auto v : e[u]) {
                    if(vis[v]) ++cnt;
                }
            }
            for(auto u : ds[i]) vis[u] = 0;
            cnt /= 2;
            if(cnt > ds[i].size()) ans2 += cnt;
        }
        printf("%d %d\n",ans1,ans2);
    }
    return 0;
}