让最多双向边->单向边（保证强连通）

78 阅读 0 评论 52 点赞

我是靠谱客的博主潇洒糖豆，最近开发中收集的这篇文章主要介绍让最多双向边->单向边（保证强连通），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

In a certain town there are n intersections connected by two- and one-way streets. The town is very modern so a lot of streets run through tunnels or viaducts. Of course it is possible to travel between any two intersections in both ways, i.e. it is possible to travel from an intersection a to an intersection b as well as from b to a without violating traffic rules. Because one-way streets are safer, it has been decided to create as much one-way traffic as possible. In order not to make too much confusion it has also been decided that the direction of traffic in already existing one-way streets should not be changed.

Your job is to create a new traffic system in the town. You have to determine the direction of traffic for as many two-way streets as possible and make sure that it is still possible to travel both ways between any two intersections.

Write a program that:

> reads a description of the street system in the town from the standard input,

> for each two-way street determines one direction of traffic or decides that the street must remain two-way,

> writes the answer to the standard output.

Input

The first line of the input contains two integers n and m, where 2 <= n <= 2000 and n-1 <= m <= n(n-1)/2. Integer n is the number of intersections in the town and interger m is the number of streets.

Each of the next m lines contains three integers a, b and c, where 1 <= a <= n, 1 <= b <= n, a != b and c belongs to {1, 2}. If c = 1 then intersections a and b are connected by an one-way street from a to
b. If c = 2 then intersections a and b are connected by a two-way street. There is at most one street
connecting any two intersections.

Process to the end of file.

Output

The output contains exactly the same number of lines as the number of two-way streets in the input.

For each such street (in any order) the program should write three integers a, b and c meaning, the new
direction of the street from a to b (c = 1) or that the street connecting a and b remains two-way (c = 2). If there are more than one solution with maximal number of one-way streets then your program should
output any of them but just one.

Sample Input

Sample Output

2 4 1
3 1 2

题意：

把尽可能多的双向边变成单向边，保证任意两点可以相互到达。

输出：
双向边变成单向边的和剩余的双向边；

那么做法是在dfs的时候，把时间戳记下来，如果对于无向边(u,v)有pre[u]<low[v]表明子孙不能回来了，我们就把这个无向边的方向标记为v->u，否则的话，就按照dfs的顺序就可以了。

代码：

//求无向图的割顶和桥
#include<cstdio>
#include<cstring>
#include<vector>
#include<iostream>
using namespace std;
const int maxn=2000000+10;
int n,m;
int dfs_clock;//时钟，每访问一个节点增1
//vector<int> G[maxn];//G[i]表示i节点邻接的所有节点
int pre[2009];//pre[i]表示i节点被第一次访问到的时间戳,若pre[i]==0表示i还未被访问
int low[2009];//low[i]表示i节点及其后代能通过反向边连回的最早的祖先的pre值
bool iscut[2009];//标记i节点是不是一个割点
typedef pair<int,int> pii;
struct State
{
int a, b, c;
State(int a = 0, int b = 0, int c = 0): a(a), b(b), c(c) {}
};
vector<pii> G[2009];
vector<State> ans;
int c[maxn];
int dfs(int u,int fa)
{
int lowu=pre[u]=++dfs_clock;
int child=0;
//子节点数目
for(int i=0; i<G[u].size(); i++)
{
int v=G[u][i].first;
int e=G[u][i].second;
if(!pre[v])
{
child++;//未访问过的节点才能算是u的孩子
int lowv=dfs(v,u);
lowu=min(lowu,lowv);
//u点是割顶
if (c[e] == 2)
{
if (lowv > pre[u])
{
ans.push_back(State(u, v, 2));
iscut[e] = 1;
}
else
ans.push_back(State(u, v, 1));
}
//printf("边(%d, %d)是桥n",u,v);
}
else if(pre[v]<pre[u] && v!=fa)//v!=fa确保了(u,v)是从u到v的反向边
{
lowu=min(lowu,pre[v]);
if(c[e]==2)
{
ans.push_back(State(u, v, 1));
}
}
}
if(fa<0 && child==1 )
iscut[u]=false;//u若是根且孩子数<=1,那u就不是割顶
return low[u]=lowu;
}
int main()
{
while(cin>>n>>m&&n&&m)
{
dfs_clock=0;//初始化时钟
memset(pre,0,sizeof(pre));
memset(iscut,0,sizeof(iscut));
for(int i=0;i<n;i++) G[i].clear();
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b>>c[i];
G[a].push_back(make_pair(b,i));
if(c[i]==2)
{
G[b].push_back(make_pair(a,i));
}
}
ans.clear();
for(int i=1;i<=n;i++)
{
if(!pre[i])
{
dfs(i,-1);
}
}
for (int i = 0; i < ans.size(); i++)
printf("%d %d %dn", ans[i].a, ans[i].b, ans[i].c);
}
}

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 2005;
const int maxm = 2 * 1e6 + 5;
typedef pair<int,int> pii;
struct State
{
int a, b, c;
State(int a = 0, int b = 0, int c = 0): a(a), b(b), c(c) {}
};
int N, M, L[maxm], R[maxm], C[maxm];
int cntlock, pre[maxn], iscut[maxm];
vector<pii> G[maxn];
vector<State> ans;
int dfs (int u, int fa)
{
int lowu = pre[u] = ++cntlock;
for (int i = 0; i < G[u].size(); i++)
{
int v = G[u][i].first, e = G[u][i].second;
if (!pre[v])
{
int lowv = dfs(v, u);
lowu = min(lowu, lowv);
if (C[e] == 2)
{
if (lowv > pre[u])
{
ans.push_back(State(u, v, 2));
iscut[e] = 1;
}
else
ans.push_back(State(u, v, 1));
}
}
else if (pre[v] < pre[u] && v != fa)
{
lowu = min(lowu, pre[v]);
if (C[e] == 2)
ans.push_back(State(u, v, 1));
}
}
return lowu;
}
void findBCC()
{
cntlock = 0;
memset(pre, 0, sizeof(pre));
memset(iscut, 0, sizeof(iscut));
for (int i = 1; i <= N; i++)
if (!pre[i]) dfs(i, -1);
}
void init ()
{
for (int i = 1; i <= N; i++) G[i].clear();
for (int i = 1; i <= M; i++)
{
scanf("%d%d%d", &L[i], &R[i], &C[i]);
G[L[i]].push_back(make_pair(R[i], i));
if (C[i] == 2)
G[R[i]].push_back(make_pair(L[i], i));
}
ans.clear();
findBCC();
}
int main ()
{
while (scanf("%d%d", &N, &M) == 2)
{
init();
for (int i = 0; i < ans.size(); i++)
printf("%d %d %dn", ans[i].a, ans[i].b, ans[i].c);
}
return 0;
}