POJ 3177 Redundant Paths(shrink nodes and bridges)

Description

N个点M条无向边，原图是连通的，现要添加一些边，使得每两点之间的路至少有两条。求最少连接几条边。

Analzye

先进行环缩点，缩点完后是一棵树。

连接任意两个节点，皆可成环。

然而连接叶子节点比连接非叶子节点更优(需添加的边较少)。

而且要连接的这两个叶子节点，其到LCA的距离越大越优。

因为：连接树(缩点后的图)中某两个距离LCA最大的叶子节点，形成的环再次缩点会缩到根节点里，这样就减少了两个点。若非如此，每次只减少一个点。

答案：假设有ans个叶子节点，每添一条边减少两个点，需要添加ans / 2条边。若ans为奇数，需要(ans + 1) / 2条边。两者可合并成后者。

如何求缩点后叶子节点的个数ans？

叶子节点特征：度数为1

方案：求桥，原图的桥是缩点后的树上的边。遍历原图每个点，对每个点遍历出边，若此出边为桥，则它所连接的两点所在的连通分量(缩点后的点)度数++。最后遍历每个缩点后的点，度数为1的是叶子节点。

Code

#include <stack>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5005;
const int M = 50005;

int n, m;

int cnt, head[N];
struct edge
{
    int v, pre;
    bool flag;
} e[M];

void add(int u, int v)
{
    e[cnt].v = v;
    e[cnt].pre = head[u];
    head[u] = cnt++;
}

stack<int> st;
bool inst[N];
int low[N], times[N], t;
int ltt[N], num, bridges;

void Tarjan(int x, int pre)
{
    st.push(x);
    inst[x] = 1;
    low[x] = times[x] = ++t;
    for(int i = head[x]; ~i; i = e[i].pre)
    {
        int to = e[i].v;
        if(to == pre)
            continue;
        if(!times[to])
        {
            Tarjan(to, x);
            low[x] = min(low[x], low[to]);
            if(low[to] > times[x])
            {
                bridges++;
                e[i].flag = e[i ^ 1].flag = 1;
            }
        }
        else if(inst[to])
            low[x] = min(low[x], times[to]);
    }
    if(low[x] == times[x])
    {
        num++;
        while(!st.empty())
        {
            int tem = st.top();
            st.pop();
            ltt[tem] = num;
            inst[tem] = 0;
            if(tem == x)
                break;
        }
    }
}

int degrees[N];

void init()
{
    while(!st.empty())
        st.pop();
    cnt = t = bridges = num = 0;
    memset(ltt, 0, sizeof(ltt));
    memset(low, 0, sizeof(low));
    memset(times, 0, sizeof(times));
    memset(inst,  0, sizeof(inst));
    memset(head, -1, sizeof(head));
    memset(degrees, 0, sizeof(degrees));
}

int main()
{
    int u, v;
    while(~scanf("%d %d", &n, &m))
    {
        init();
        for(int i = 0; i < m; ++i)
        {
            scanf("%d %d", &u, &v);
            add(u, v);
            add(v, u);
        }

        Tarjan(1, -1);///Original graph is connected.

        for(int i = 1; i <= n; ++i)
            for(int j = head[i]; ~j; j = e[j].pre)
                if(e[j].flag)
                    degrees[ ltt[i] ]++;

        int ans = 0;
        for(int i = 1; i <= num; ++i)
            if(degrees[i] == 1)
                ans++;
        cout << (ans + 1) / 2 << '\n';
    }
    return 0;
}

Something

有向图的环缩点可以是Tarjan(int x)，利用vis[]协助。

无向图的环缩点需要是Tarjan(int x, int pre)，避免遍历到反向边。

关于避免访问到反向边而又不错过重边：

正常情况下：

Tarjan(int x, int pre_edge)配合if(i == (pre_edge ^ 1))continue;

如果原图保证没有重边，可以偷懒：

Tarjan(int x, int pre_node)配合if(to == pre_node)continue;