欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ 3177 Redundant Paths(求桥)

程序员文章站 2022-05-27 16:24:57
...
题目链接
题意

给你一个联通图,求最小加几条边,使图变成双连通图

思路

求桥,将双连通分量缩点,以桥为边构成新图,图中度数为1的节点都需要加边,所以答案为度数为1节点除以2向上取整。

总结

无多重边,只需记录父节点,判断是否走回去即可
多重边求桥链式前向星建图,通过同一条边id差1避免同一条边重复遍历

代码
#include <stdio.h>
#include <string.h>
#include <vector>
#include <stack>
using namespace std;

vector<int> e[5005];
stack<int> sta;
int d[5005], dfn[5005], low[5005], tim, col[5005], x[5005][2], cnt, bri;

void tarjan(int u, int fa)
{
    sta.push(u);
    dfn[u] = low[u] = ++tim;
    for(int i = 0; i < e[u].size(); ++i)
    {
        int v = e[u][i];
        if(!dfn[v])
        {
            tarjan(v,u);
            low[u] = min(low[u], low[v]);
            if(low[v] > dfn[u]) x[bri][0] = u, x[bri++][1] = v;
        }
        else if(v != fa) low[u] = min(low[u], dfn[v]); // 判断防止回头,真滴巧妙
    }
    if(dfn[u] == low[u])
    {
        ++cnt;
        while(1)
        {
            int now = sta.top();
            sta.pop();
            col[now] = cnt;
            if(now == u) break;
        }
    }
}

int main()
{
    int n, m;
    while(~scanf("%d%d",&n,&m))
    {
        for(int i = 1; i <= n; ++i) e[i].clear();
        while(m--)
        {
            int u, v;
            scanf("%d%d",&u,&v);
            e[v].push_back(u);
            e[u].push_back(v);
        }
        for(int i = 1; i <= n; ++i) d[i] = dfn[i] = low[i] = 0;
        while(!sta.empty()) sta.pop();
        tim = 0;
        cnt = 0;
        bri = 0;
        tarjan(1,-1);
        int ans = 0;
        for(int i = 0; i < bri; ++i) ++d[col[x[i][0]]], ++d[col[x[i][1]]];
        for(int i = 1; i <= cnt; ++i) if(d[i] == 1) ++ans;
        printf("%d\n",(ans+1)/2);
    }
    return 0;
}
相关标签: tarjan