题意分析

这道题目描述了一个城市交通网络的问题，我们需要将双向街道尽可能多地转换为单向街道，同时确保交通网络的强连通性（即从任何一个路口出发，可以到达所有其他路口）。具体要求如下：

1. 输入：

   • 多个测试用例，每个用例给出一个无向图（城市交通网络）。
   • 图的顶点（路口）数量为 n，边（街道）数量为 m。
   • 每条边是双向的，且输入中只会出现一次（即如果输入 i j，不会出现 j i）。
   • 每个顶点的度数不超过 4（即每个路口最多连接 4 条街道）。
   • 图是连通的（初始时双向街道可以保证任意两个路口之间可以互相到达）。

2. 输出：

   • 对每条边，尝试将其转换为单向边（i j 或 j i）。
   • 如果必须保留双向边才能保证强连通性，则输出两个方向（i j 和 j i）。
   • 输出可以是任意合法的解（即满足强连通性的任意方向分配方案）。

3. 目标：

   • 最大化单向边的数量（即尽可能少地保留双向边）。

解题思路

1. 问题本质

我们需要将无向图转换为有向图，且该有向图是强连通的。强连通图的要求是：对于任意两个顶点 u 和 v，存在从 u 到 v 的路径。

2. 关键观察

• 无向图的边可以看作两条方向相反的有向边。
• 强连通性的要求意味着我们需要选择一个边的方向分配方案，使得图是强连通的。
• 如果原无向图中存在桥（即删除后图不连通的边），则该边必须保留双向（否则会破坏连通性）。
• 对于非桥边（即属于某个环的边），可以分配为单向边。

3. 算法选择

• Tarjan 算法：用于找到无向图中的桥（割边）和双连通分量。
  • 桥必须保留双向，否则会破坏连通性。
  • 非桥边可以分配为单向边（只要保证强连通性）。
• DFS 或 BFS：用于验证强连通性。
• 边方向分配：
  • 对于非桥边，可以尝试分配方向（例如按照 DFS 树的方向）。
  • 对于桥边，必须保留双向。

4. 具体步骤

1. 输入处理：读取无向图。
2. 找桥：使用 Tarjan 算法标记所有桥边。
3. 构建有向图：
   • 对于非桥边，分配方向（例如按照 DFS 遍历的顺序）。
   • 对于桥边，保留双向。
4. 验证强连通性：检查是否有顶点无法到达其他顶点。
5. 输出结果：按照方向分配输出边。

C++代码实现

#include<iostream> 
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1010, M = 2000010;

struct Edge {
    int u, v, next;
    bool vis, cut, left;
} ed[M];

int n, m, t = 1, tot, idx;
int head[N], dfn[N], low[N];

void add(int u, int v) {
    ed[tot] = {u, v, head[u], false, false, false};
    head[u] = tot++;
}

void tarjan(int u) {
    dfn[u] = low[u] = ++idx;
    for(int i = head[u]; ~i; i = ed[i].next) {
        int v = ed[i].v;
        if(ed[i].vis) continue;
        ed[i].vis = ed[i^1].vis = true;
        if(dfn[v] == -1) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if(dfn[u] < low[v]) {
                ed[i].cut = ed[i^1].cut = true;
                ed[i].left = ed[i^1].left = true;
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

void dfs(int u) {
    dfn[u] = low[u] = ++idx;
    for(int i = head[u]; ~i; i = ed[i].next) {
        if(ed[i].cut) continue;
        int v = ed[i].v;
        if(dfn[v] == -1) {
            ed[i].vis = ed[i^1].vis = true;
            dfs(v);
            low[u] = min(low[u], low[v]);
            if(low[v] > dfn[u]) 
                ed[i^1].left = true;
            else 
                ed[i].left = true;
        } else {
            low[u] = min(low[u], dfn[v]);
            if(!ed[i].vis) ed[i].left = true;
            ed[i].vis = ed[i^1].vis = true;
        }
    }
}

void solve() {
    memset(dfn, -1, sizeof(dfn));
    idx = 0;
    tarjan(1);
    memset(dfn, -1, sizeof(dfn));
    idx = 0;
    for(int i = 0; i < tot; i++) ed[i].vis = false;
    for(int i = 1; i <= n; i++) 
        if(dfn[i] == -1) dfs(i);
}

int main() {
    while(~scanf("%d%d", &n, &m)) {
        if(!n && !m) break;
        tot = 0;
        memset(head, -1, sizeof(head));
        for(int i = 1; i <= m; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            add(u, v);
            add(v, u);
        }
        solve();
        printf("%d\n\n", t++);
        for(int i = 0; i < tot; i++) 
            if(ed[i].left) printf("%d %d\n", ed[i].u, ed[i].v);
        printf("#\n");
    }
    return 0;
}

题意分析

题目要求将双向街道网络转换为单向街道网络，同时保持图的强连通性。关键点包括：

1. 需要识别图中的桥（关键边），这些边必须保持双向通行
2. 非桥边可以改为单向通行
3. 必须确保转换后的图中任意两点仍相互可达

解题思路

1. 桥检测：使用Tarjan算法识别所有桥
2. 边定向：
   • 桥边必须保留双向通行
   • 非桥边可以定向为单向
3. DFS遍历：确定非桥边的方向，保持强连通性

实现步骤

1. 输入处理：
   • 读取$n$（节点数）和$m$（边数）
   • 构建无向图的邻接表
2. Tarjan算法：
   • 计算每个节点的$dfn$和$low$值
   • 标记所有桥边
3. DFS定向：
   • 对非桥边进行定向
   • 确保不破坏图的连通性
4. 输出结果：
   • 输出桥边双向
   • 输出非桥边单向

C++实现

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1010, M = 2000010;

struct Edge {
    int u, v, next;
    bool vis, cut, left;
} ed[M];

int n, m, t = 1, tot, idx;
int head[N], dfn[N], low[N];

void add(int u, int v) {
    ed[tot] = {u, v, head[u], false, false, false};
    head[u] = tot++;
}

void tarjan(int u) {
    dfn[u] = low[u] = ++idx;
    for(int i = head[u]; ~i; i = ed[i].next) {
        int v = ed[i].v;
        if(ed[i].vis) continue;
        ed[i].vis = ed[i^1].vis = true;
        if(dfn[v] == -1) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if(dfn[u] < low[v]) {
                ed[i].cut = ed[i^1].cut = true;
                ed[i].left = ed[i^1].left = true;
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

void dfs(int u) {
    dfn[u] = low[u] = ++idx;
    for(int i = head[u]; ~i; i = ed[i].next) {
        if(ed[i].cut) continue;
        int v = ed[i].v;
        if(dfn[v] == -1) {
            ed[i].vis = ed[i^1].vis = true;
            dfs(v);
            low[u] = min(low[u], low[v]);
            if(low[v] > dfn[u]) 
                ed[i^1].left = true;
            else 
                ed[i].left = true;
        } else {
            low[u] = min(low[u], dfn[v]);
            if(!ed[i].vis) ed[i].left = true;
            ed[i].vis = ed[i^1].vis = true;
        }
    }
}

void solve() {
    memset(dfn, -1, sizeof(dfn));
    idx = 0;
    tarjan(1);
    memset(dfn, -1, sizeof(dfn));
    idx = 0;
    for(int i = 0; i < tot; i++) ed[i].vis = false;
    for(int i = 1; i <= n; i++) 
        if(dfn[i] == -1) dfs(i);
}

int main() {
    while(~scanf("%d%d", &n, &m)) {
        if(!n && !m) break;
        tot = 0;
        memset(head, -1, sizeof(head));
        for(int i = 1; i <= m; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            add(u, v);
            add(v, u);
        }
        solve();
        printf("%d\n\n", t++);
        for(int i = 0; i < tot; i++) 
            if(ed[i].left) printf("%d %d\n", ed[i].u, ed[i].v);
        printf("#\n");
    }
    return 0;
}

代码说明

1. 数据结构：
   • Edge结构体存储边信息及状态标记
   • dfn和low数组用于Tarjan算法
2. 核心算法：
   • tarjan()：识别图中的桥
   • dfs()：确定非桥边的方向
3. 关键处理：
   • 桥边标记为双向（cut=true）
   • 非桥边根据DFS遍历顺序定向
4. 复杂度分析：
   • 时间复杂度：$O(n+m)$
   • 空间复杂度：$O(n+m)$
5. 示例分析：
   • 输入样例1中的桥边保持双向
   • 非桥边根据DFS顺序定向