首页 > 代码库 > UVA 610 - Street Directions(割边)
UVA 610 - Street Directions(割边)
UVA 610 - Street Directions
题目链接
题意:给定一个无向图,要求把尽可能多的边定向,使得形成一个强连通图,输出定向后的图,不能定向的边就变成两条有向边
思路:找出割边,只有割边是需要定成两条的,其他的双连通分量中,边肯定都可以定向,然后在dfs不经过割边打印路径,最后在打印出割边(拆成两条)
代码:
#include <cstdio> #include <cstring> #include <vector> using namespace std; const int N = 1005; int n, m; struct Edge { int u, v, id; int fan; bool iscut, used; Edge() {} Edge(int u, int v, int id, int fan) { this->u = u; this->v = v; this->id = id; this->fan = fan; used = false; iscut = false; } }; int pre[N], low[N], dfs_clock; vector<Edge> g[N]; vector<Edge> cut; int dfs(int u, int fa) { int lowu = pre[u] = ++dfs_clock; for (int i = 0; i < g[u].size(); i++) { int v = g[u][i].v; int id = g[u][i].id; if (id == fa) continue; if (!pre[v]) { int lowv = dfs(v, id); lowu = min(lowu, lowv); if (lowv > pre[u]) { cut.push_back(g[u][i]); g[u][i].iscut = true; g[v][g[u][i].fan].iscut = true; } } else lowu = min(lowu, pre[v]); } return low[u] = lowu; } void find_cut(int n) { cut.clear(); memset(pre, 0, sizeof(pre)); dfs_clock = 0; for (int i = 0; i < n; i++) { if (!pre[i]) { dfs(i, 0); } } } int vis[N]; void print(int u) { vis[u] = 1; for (int i = 0; i < g[u].size(); i++) { if (g[u][i].iscut) continue; if (g[u][i].used) continue; int v = g[u][i].v; g[u][i].used = true; g[v][g[u][i].fan].used = true; printf("%d %d\n", u + 1, v + 1); if (vis[v]) continue; print(v); } } int main() { int cas = 0; while (~scanf("%d%d", &n, &m) && n || m) { int u, v; for (int i = 0; i < n; i++) g[i].clear(); for (int i = 1; i <= m; i++) { scanf("%d%d", &u, &v); u--; v--; g[u].push_back(Edge(u, v, i, g[v].size())); g[v].push_back(Edge(v, u, i, g[u].size() - 1)); } find_cut(n); printf("%d\n\n", ++cas); memset(vis, 0, sizeof(vis)); for (int i = 0; i < n; i++) if (!vis[i]) print(i); for (int i = 0; i < cut.size(); i++) { printf("%d %d\n", cut[i].u + 1, cut[i].v + 1); printf("%d %d\n", cut[i].v + 1, cut[i].u + 1); } printf("#\n"); } return 0; }
UVA 610 - Street Directions(割边)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。