首页 > 代码库 > 【连通图|边双连通+缩点】POJ-3177 Redundant Paths

【连通图|边双连通+缩点】POJ-3177 Redundant Paths

2024-08-10 08:13:00   216人阅读

Redundant Paths
Time Limit: 1000MS Memory Limit: 65536K
   

Description

In order to get from one of the F (1 <= F <= 5,000) grazing fields (which are numbered 1..F) to another field, Bessie and the rest of the herd are forced to cross near the Tree of Rotten Apples. The cows are now tired of often being forced to take a particular path and want to build some new paths so that they will always have a choice of at least two separate routes between any pair of fields. They currently have at least one route between each pair of fields and want to have at least two. Of course, they can only travel on Official Paths when they move from one field to another. 

Given a description of the current set of R (F-1 <= R <= 10,000) paths that each connect exactly two different fields, determine the minimum number of new paths (each of which connects exactly two fields) that must be built so that there are at least two separate routes between any pair of fields. Routes are considered separate if they use none of the same paths, even if they visit the same intermediate field along the way. 

There might already be more than one paths between the same pair of fields, and you may also build a new path that connects the same fields as some other path.

Input

Line 1: Two space-separated integers: F and R 

Lines 2..R+1: Each line contains two space-separated integers which are the fields at the endpoints of some path.

Output

Line 1: A single integer that is the number of new paths that must be built.

Sample Input

7 7
1 2
2 3
3 4
2 5
4 5
5 6
5 7

Sample Output

2

Hint

Explanation of the sample: 

One visualization of the paths is: 
   1   2   3
   +---+---+  
       |   |
       |   |
 6 +---+---+ 4
      / 5
     / 
    / 
 7 +
Building new paths from 1 to 6 and from 4 to 7 satisfies the conditions. 
   1   2   3
   +---+---+  
   :   |   |
   :   |   |
 6 +---+---+ 4
      / 5  :
     /     :
    /      :
 7 + - - - -
Check some of the routes: 
1 – 2: 1 –> 2 and 1 –> 6 –> 5 –> 2 
1 – 4: 1 –> 2 –> 3 –> 4 and 1 –> 6 –> 5 –> 4 
3 – 7: 3 –> 4 –> 7 and 3 –> 2 –> 5 –> 7 
Every pair of fields is, in fact, connected by two routes. 

It‘s possible that adding some other path will also solve the problem (like one from 6 to 7). Adding two paths, however, is the minimum.
————————————————————————————————————————————————————————————————————————————————————————————————
题意：给出一个无向图，保证是连通的，问要把这个无向图变成边双连通图需要至少修建几条新路。
思路：首先如何求出边双连通分量？方法比点双连通分量要简单地多：
首先求一次图中的桥，然后用flood_fill法染色，保证dfs的时候不经过桥即可。

”一个有桥的连通图，如何把它通过加边变成边双连通图？方法为首先求出所有的桥，然后删除这些桥边，剩下的每个连通块都是一个双连通子图。把每个双连通子图收缩为一个顶点，再把桥边加回来，最后的这个图一定是一棵树，边连通度为1。

统计出树中度为1的节点的个数，即为叶节点的个数，记为leaf。则至少在树上添加(leaf+1)/2条边，就能使树达到边双连通，所以至少添加的边数就是(leaf+1)/2。具体方法为，首先把两个最近公共祖先最远的两个叶节点之间连接一条边，这样可以把这两个点到祖先的路径上所有点收缩到一起，因为一个形成的环一定是双连通的。然后再找两个最近公共祖先最远的两个叶节点，这样一对一对找完，恰好是(leaf+1)/2次，把所有点收缩到了一起。“ --BYVoid

然后是缩点统计每个新点的度数：
将输入的边保存起来，取出两个点的bcc_id，如果相同则说明处于同一个连通分量里面。否则统计度数。
这就是缩点的思想：用颜色（id）代替点。
注意！！！
网上有很多代码并不正确，尤其是通过“相同的low值”什么的那种写法：
“……代码的写法确实有问题，因为在同一个双连通分量中的点的low值并不一定相等，所以使用low值来判断是否在同一个分量中显然是有问题的。因此我们最安全的做法时在tarjan的过程中，把桥标记出来，然后使用dfs跑每一个连通分量……” --Bright-Thinking
P.S. 网上可以找到很多不判断重边的代码，我觉得是因为测试数据里面没有重边，但是也可能是因为缩点的缘故，不太清楚。反正判断重边也不麻烦，加上也是0msAC。
代码如下：
/*
 * ID: j.sure.1
 * PROG:
 * LANG: C++
 */
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <climits>
#include <iostream>
#define Mem(f, x) memset(f, x, sizeof(f))
#define PB push_back
#define LL long long
using namespace std;
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
/****************************************/
const int N = 5e3+5, M = 2e4+5;
struct Edge {
    int v, next, idx, tag;
    Edge(){}
    Edge(int _v, int _next, int _idx, int _tag = 0):
        v(_v), next(_next), idx(_idx), tag(_tag){}
}e[M];
int n, m, deep, tot, bcc_cnt;
int dfn[N], head[N], bcc_id[N], line[N][2], deg[N];
bool isbri[M];

void __init__()
{
    bcc_cnt = tot = deep = 0;
    for(int i = 0; i < n; i++) {
        head[i] = -1;
        deg[i] = dfn[i] = bcc_id[i] = 0;
    }
    Mem(isbri, 0);
}

void add(int u, int v, int idx)
{
    int p;
    for(p = head[u]; ~p; p = e[p].next) {
        if(e[p].v == v) {
            e[p].tag++;
            return ;
        }
    }
    e[tot] = Edge(v, head[u], idx);
    head[u] = tot++;
}

int dfs(int u, int fa)
{
    int lowu = dfn[u] = ++deep;
    for(int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].v;
        if(!dfn[v]) {
            int lowv = dfs(v, u);
            lowu = min(lowu, lowv);
            if(lowv > dfn[u] && !e[i].tag) 
                isbri[e[i].idx] = 1;
        }
        else if(dfn[v] < dfn[u] && v != fa)
            lowu = min(lowu, dfn[v]);
    }
    return lowu;
}

void flood(int u) 
{
    bcc_id[u] = bcc_cnt;
    for(int i = head[u]; ~i; i = e[i].next) {
        if(isbri[e[i].idx]) continue ;
        int v = e[i].v;
        if(!bcc_id[v]) {
            flood(v);
        }
    }
}

int main()
{
#ifdef J_Sure
    freopen("000.in", "r", stdin);
    //freopen("999.out", "w", stdout);
#endif
    while(~scanf("%d%d", &n, &m)) {
        int ID = 0;
        __init__();
        for(int i = 0; i < m; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            u--; v--;
            line[i][0] = u; line[i][1] = v;
            add(u, v, ID);
            add(v, u, ID++);
        }
        dfs(0, -1);
        for(int i = 0; i < n; i++) {
            if(!bcc_id[i]) {
                bcc_cnt++;
                flood(i);
            }
        }
        for(int i = 0; i < m; i++) {
            int u = bcc_id[line[i][0]], v = bcc_id[line[i][1]];
            if(u != v) {
                deg[u]++; deg[v]++;
            }
        }
        int ans = 0;
        for(int i = 1; i <= bcc_cnt; i++) {
            if(deg[i] == 1) ans++;
        }
        printf("%d\n", (ans+1)/2);
    }
    return 0;
}


【连通图|边双连通+缩点】POJ-3177 Redundant Paths


联系
我们