目录
1 问题描述
1310 One-way traffic In a certain town there are n intersections connected by two- and one-way streets. The town is verymodern so a lot of streets run through tunnels or viaducts. Of course it is possible to travel betweenany two intersections in both ways, i.e. it is possible to travel from an intersection a to an intersectionb as well as from b to a without violating traffic rules. Because one-way streets are safer, it has beendecided to create as much one-way traffic as possible. In order not to make too much confusion it hasalso 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 oftraffic for as many two-way streets as possible and make sure that it is still possible to travel both waysbetween 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 remaintwo-way,• writes the answer to the standard output. InputThe 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 integer 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 andc belongs to { 1, 2}. If c = 1 then intersections a and b are connected by an one-way street from a tob. If c = 2 then intersections a and b are connected by a two-way street. There is at most one streetconnecting any two intersections. OutputThe 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 newdirection 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 shouldoutput any of them but just one. Sample Input4 44 1 14 2 21 2 11 3 2 Sample Output2 4 13 1 2
题目链接：
2 解决方案
首先看看关于图论的割点和桥的相关概念定义：
引用文末参考资料1：
1.割点：若删掉某点后，原连通图分裂为多个子图，则称该点为割点。
2.割点集合：在一个无向连通图中，如果有一个顶点集合，删除这个顶点集合，以及这个集合中所有顶点相关联的边以后，原图变成多个连通块，就称这个点集为割点集合。
3.点连通度：最小割点集合中的顶点数。
4.割边(桥)：删掉它之后，图必然会分裂为两个或两个以上的子图。
5.割边集合：如果有一个边集合，删除这个边集合以后，原图变成多个连通块，就称这个点集为割边集合。
6.边连通度：一个图的边连通度的定义为，最小割边集合中的边数。
7.缩点：把没有割边的连通子图缩为一个点，此时满足任意两点之间都有两条路径可达。
注：求块<>求缩点。缩点后变成一棵k个点k-1条割边连接成的树。而割点可以存在于多个块中。
8.双连通分量：分为点双连通和边双连通。它的标准定义为：点连通度大于1的图称为点双连通图，边连通度大于1的图称为边双连通图。通俗地讲，满足任意两点之间，能通过两条或两条以上没有任何重复边的路到达的图称为双连通图。无向图G的极大双连通子图称为双连通分量。
具体代码如下：
package com.liuzhen.practice;import java.util.ArrayList;import java.util.Scanner;import java.util.Stack;public class Main { public static int n; //给定图的顶点数 public static int count; //记录遍历次序 public static int[] DFN; public static int[] Low; public static int[] parent; //parent[i] = j，表示顶点i的直接父母顶点为j public static Stack stack; public static ArrayList [] map; public static ArrayList ans; //存储最终输出结果 static class edge { public int a; //边的起点 public int b; //边的终点 public int c; //c = 1表示单向边，c = 2表示双向边 public edge(int a, int b, int c) { this.a = a; this.b = b; this.c = c; } } @SuppressWarnings("unchecked") public void init() { count = 0; DFN = new int[n + 1]; Low = new int[n + 1]; parent = new int[n + 1]; stack = new Stack (); map = new ArrayList[n + 1]; ans = new ArrayList (); for(int i = 1;i <= n;i++) { DFN[i] = -1; Low[i] = -1; parent[i] = -1; map[i] = new ArrayList (); } } public void TarJan(int start, int father) { DFN[start] = count++; Low[start] = DFN[start]; parent[start] = father; stack.push(start); for(int i = 0;i < map[start].size();i++) { edge temp = map[start].get(i); int j = temp.b; if(DFN[j] == -1) { TarJan(j, start); Low[start] = Math.min(Low[start], Low[j]); if(temp.c == 2) { if(Low[j] > DFN[start]) { //当边temp为割边(或者桥)时 ans.add(temp); } else { ans.add(new edge(temp.a, temp.b, 1)); } } } else if(j != parent[start]) { //当j不是start的直接父母节点时 Low[start] = Math.min(Low[start], DFN[j]); if(temp.c == 2) { ans.add(new edge(temp.a, temp.b, 1)); } } } } public void getResult() { for(int i = 1;i <= n;i++) { if(parent[i] == -1) TarJan(i, 0); } for(int i = 0;i < ans.size();i++) System.out.println(ans.get(i).a+" "+ans.get(i).b+" "+ans.get(i).c); } public static void main(String[] args) { Main test = new Main(); Scanner in = new Scanner(System.in); n = in.nextInt(); int k = in.nextInt(); test.init(); for(int i = 0;i < k;i++) { int a = in.nextInt(); int b = in.nextInt(); int c = in.nextInt(); map[a].add(new edge(a, b, c)); if(c == 2) map[b].add(new edge(b, a, c)); } test.getResult(); }}
运行结果：
4 44 1 14 2 21 2 11 3 22 4 11 3 2
参考资料：
1.
2.
3.