UVa 610 - Street Directions

#图论 #边-双联通
Published on 2015-12-15

题目地址

描述

有 n(n≤1000)n(n\le1000) 个节点，另有 mm 条双向道路。任务是将尽可能多的道路改造成单向道路，使得改造后的图仍然联通（每个节点相互可达）。

样例输入

7 10
1 2
1 3
2 4
3 4
4 5
4 6
5 7
6 7
2 5
3 6
7 9
1 2
1 3
1 4
2 4
3 4
4 5
5 6
5 7
7 6
0 0

样例输出

1

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

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

分析

初始的图是无向图，那么 u→vu\rightarrow v 至少得有两条不重叠的道路，才可以使改成无向边之后 u→v,v→uu\rightarrow v,v\rightarrow u 至少有一条路径。那么算法已经清晰了，对无向图求边-双连通分量，找出桥所有的桥即可。所有的桥必须是双向道路，其余的都可以改造成单向道路。
打印顺序是任意的，我们先用 DFS 顺着打印路径，不走重边（包括反边），不走桥，用类似欧拉回路的方法不停地找环。这样就可以将原先每个边-双连通分量内部所有点强连通，最后打出所有桥，使得全图强连通。

代码

//  Created by Sengxian on 12/15/15.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 610 双连通+割边
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
using namespace std;
const int maxn = 1000 + 3;
struct edge {
    int to, iscut, rev, used;
    edge(int to, int iscut, int rev, int used): to(to), iscut(iscut), rev(rev), used(used) {}
    edge() {}
};
vector<edge> G[maxn];
vector<pair<int, int> > cuts;
int n, m, pre[maxn], timestamp;
bool vis[maxn];

int dfs(int u, int fa) {
    int lowu = pre[u] = ++timestamp;
    for(int i = 0; i < G[u].size(); ++i) {
        edge &e = G[u][i];
        int v = e.to;
        if(!pre[v]) {
            int lowv = dfs(v, u);
            lowu = min(lowu, lowv);
            if(lowv > pre[u]) {
                e.iscut = true;
                G[e.to][e.rev].iscut = true;
                cuts.push_back(make_pair(u, v));
            }
        }else if(pre[v] < pre[u] && v != fa) lowu = min(lowu, pre[v]);
    }
    return lowu;
}

void find_bcc() {
    cuts.clear();
    memset(pre, 0, sizeof(pre));
    timestamp = 0;
    for(int i = 0; i < n; ++i)
        if(!pre[i]) dfs(i, 0);
}

void print(int x) {
    vis[x] = true;
    for(int i = 0; i < G[x].size(); ++i) {
        edge &e = G[x][i];
        if(e.iscut || e.used) continue;
        e.used = true;
        G[e.to][e.rev].used = true;
        printf("%d %d\n", x + 1, e.to + 1);
        if(!vis[e.to]) print(e.to); //不走重复路！
    }
}

inline int ReadInt() {
    int n = 0, ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    do {
        n = n * 10 + ch - '0';
        ch = getchar();
    }while(ch >= '0' && ch <= '9');
    return n;
}

int main() {
    int caseNum = 0, f, t;
    while(n = ReadInt(), m = ReadInt()) {
        for(int i = 0; i < n; ++i) G[i].clear();
        printf("%d\n\n", ++caseNum);
        for(int i = 0; i < m; ++i) {
            f = ReadInt() - 1, t = ReadInt() - 1;
            G[f].push_back(edge(t, 0, G[t].size(), 0));
            G[t].push_back(edge(f, 0, G[f].size() - 1, 0));
        }
        find_bcc();
        memset(vis, 0, sizeof(vis));
        for(int i = 0; i < n; ++i)
            if(!vis[i]) print(i);
        //割边必须双向，否则图不能连通
        for(int i = 0; i < cuts.size(); ++i)
            printf("%d %d\n%d %d\n", cuts[i].first + 1, cuts[i].second + 1, cuts[i].second + 1, cuts[i].first + 1);
        printf("# \n");
    }
}
边－双联通分量四题