UVA610 - Street Directions(Tarjan)
Tarjan
2023-09-14 09:10:10 时间
题意: 给出一张无向图,尽量多的使边成为单向边。改变之后的图仍然强连通。
思路:找出全部的桥。桥肯定是不能改变成为单向边。之后不是桥的边能组成n个连通块。依照dfs的顺序规定方向就可以。
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <utility> #include <algorithm> using namespace std; const int MAXN = 10005; struct Edge{ int to, next; bool cut, vis; }edge[MAXN * 10]; int head[MAXN], tot; int Low[MAXN], DFN[MAXN]; int Index, top; int bridge; vector<pair<int, int> > ans; void addedge(int u, int v) { edge[tot].to = v; edge[tot].next = head[u]; edge[tot].vis = false; head[u] = tot++; } void Tarjan(int u, int pre) { int v; Low[u] = DFN[u] = ++Index; for (int i = head[u]; i != -1; i = edge[i].next) { v = edge[i].to; if (v == pre) continue; if (edge[i].vis) continue; edge[i].vis = edge[i^1].vis = true; ans.push_back(make_pair(u, v)); if (!DFN[v]) { Tarjan(v, u); if (Low[u] > Low[v]) Low[u] = Low[v]; if (Low[v] > DFN[u]) { ans.push_back(make_pair(v, u)); } } else if (Low[u] > DFN[v]) Low[u] = DFN[v]; } } void init() { memset(head, -1, sizeof(head)); memset(DFN, 0, sizeof(DFN)); tot = Index = 0; } int main() { int n, m, t = 1; while (scanf("%d%d", &n, &m)) { if (n == 0 && m == 0) break; init(); int u, v; for (int i = 0; i < m; i++) { scanf("%d%d", &u, &v); addedge(u, v); addedge(v, u); } ans.clear(); for (int i = 1; i <= n; i++) { if (!DFN[i]) Tarjan(i, i); } printf("%d\n\n", t++); for (int i = 0; i < ans.size(); i++) printf("%d %d\n", ans[i].first, ans[i].second); printf("#\n"); } return 0; }
相关文章
- UVAoj 11324 - The Largest Clique(tarjan + dp)
- Java实现有向图强连通分量的Tarjan算法
- Java实现有向图强连通分量的Tarjan算法
- Java实现有向图强连通分量的Tarjan算法
- Java实现有向图强连通分量的Tarjan算法
- Java实现有向图强连通分量的Tarjan算法
- 【37.48%】【hdu 2587】How far away ?(3篇文章,3种做法,LCA之Tarjan算法)
- Tarjan:这个算法大神
- tarjan+缩点+强连通定理
- tarjan强连通分量
- 13.2 Tarjan算法
- POJ1330Nearest Common Ancestors——近期公共祖先(离线Tarjan)
- UVa 12587 Reduce the Maintenance Cost(Tarjan + 二分 + DFS)
- POJ 1330 Nearest Common Ancestors(Tarjan离线LCA)
- ZOJ 3795 Grouping(Tarjan收缩点+DAG)
- hdu1269迷宫城堡 (强连通Tarjan+邻接表)
- 刷题记录:牛客NC20284[SCOI2011]糖果 tarjan+差分约束+拓扑排序