【u209】轰炸

Time Limit: 1 second

Memory Limit: 128 MB

【问题描述】

小y是苏联的总书记。

苏联有n个城市，某些城市之间修筑了公路。任意两个城市都可以通过公路直接或者间接到达。

小y发现有些公路被毁坏之后会造成某两个城市之间无法互相通过公路到达。这样的公路就被称为dangerous pavement。

为了防止美帝国对dangerous pavement进行轰炸，造成某些城市的地面运输中断，小y决定在所有的dangerous pavement驻扎重兵。可是到

底哪些是dangerous pavement呢？你的任务就是找出所有这样的公路。

【输入格式】

第一行n，m(1<=n<=150, 1<=m<=5000)，分别表示有n个城市，总共m条公路。以下m行,每行两个整数a, b，表示城市a和城市b之间修筑了直接的公路。

【输出格式】

输出有若干行。每行包含两个数字a,b(a<b)，表示是dangerous pavement。请注意：输出时，所有的数对必须按照a从小到大排序输出；如果a相同，则根据b从小到大排序。

Sample Input1

Sample Output1

 1 2

5 6

【题解】

	这道题用tarjan来做。

	tarjan的作用在于缩点。即把那些能够互相到达的点给缩成一个点。比如下图



	上图中的2,3,4,5为一个强连通分量。每两个点之间都有两条路径可以到达。所以不会满足重要公路的定义。

	然后执行完tarjan算法之后。

	1,2,3,4,5,6的新编号会变为3,2,2,2,2,1。

	则对于每一条边。

	只要bianhao[x]!=bianhao[y]。这条路径就是一条重要路径。

	这里的bianhao[i]是缩点结束之后i新的编号；

	然后一开始把输入的点按照题目的要求用比较函数排序就好

	一开始不能写using namespace std;

	因为好像next在加入上面这一句之后变成一个关键字了。

	除了tarjan算法之外。你也可以枚举所有的边。假设其是关键路径。然后尝试着删掉它。然后

	就从任意一个点开始遍历。看一下能不能到达所有的节点.如果不能则是关键路径否则不是。我之前做的时候

	是这样做的。好像可以过。

	当然。下面只提供tarjan算法的程序。

【代码】

#include <cstdio> 

#include <cstring>

#include <algorithm> //sort函数包含在algorithm头文件当中

struct bian //这个结构体是为了方便排序。

{

	int x, y;

};

bian a[5001]; //这是5000条边

int n, m, first[151], next[10001], en[10001], totm = 0, w[151][151] = { 0 }; //用邻接表来存储某个点的出度信息

int dfn[151], low[151], num = 0, stack[151], zzz[151], tot = 0, bianhao[151];//这是用于实现tarjan算法的数组

//zzz[i]表示i号节点在栈中的位置。

bool flag[151]; //记录某个节点是否访问过。

void input_data()

{

	scanf("%d%d", &n, &m);//输入n个点m条边

	for (int i = 1; i <= m; i++)

	{

		int x, y;

		scanf("%d%d", &x, &y);

		if (x > y) //因为要求输出的时候小的输出在前面。所以在输入的时候就进行一下处理。

		{

			int t = x; x = y; y = t;

		}

		a[i].x = x;//用邻接表来存储这张图。

		a[i].y = y;

		w[x][y] = w[y][x] = 1;

		totm++;

		next[totm] = first[x];

		first[x] = totm;

		en[totm] = y;

		totm++;

		next[totm] = first[y];

		first[y] = totm;

		en[totm] = x;

	}

}

int min(int a, int b) //获取a和b中的较小值。

{

	return a > b ? b : a;

}

void push(int what) //把x这个元素放入栈顶。同时记录这个元素在栈中的位置。

{

	stack[0]++;

	stack[stack[0]] = what;

	zzz[what] = stack[0];

}

void pop(int what) //把栈顶元素到what这个元素从栈中弹出来。栈指针指向what下面的元素

{ //这些弹出来的元素就属于同一个强连通分量

	tot++; //递增编号

	int tt = zzz[what] - 1; //改变栈指针的位置 先不赋值给stack[0],因为我们等下要用到stack[0]且zzz[what]会发生改变。

	for (int i = zzz[what]; i <= stack[0]; i++) //把这些元素弹出

	{

		bianhao[stack[i]] = tot;//它们拥有同样的新编号。

		zzz[stack[i]] = 0;//它们不在栈中了。所以改为0;

	}

	stack[0] = tt;//改变栈的指针。

}

void tarjan(int x) //tarjan的递归程序

{

	flag[x] = true; //进入之后把这个点标记为已经走过。

	num++; //这是用来给dfn和low编号的

	dfn[x] = low[x] = num; //df序

	push(x);//把x这个元素加入到栈顶

	int temp = first[x]; //获取它最后一次出现的位置

	while (temp != 0) //如果还有出度

	{

		int y = en[temp]; //获取它的出度

		if (w[x][y] == 0) //如果刚才已经走过这条边就不走了。

		{

			temp = next[temp];

			continue;

		}

		w[x][y] = 0; //双向图。不能让他从x走到y又从y走到x。

		w[y][x] = 0; //如果有重边的话要改成递减。

		if (!flag[y]) //如果还没有访问过这个出度

		{

			tarjan(y); //则访问它

			low[x] = min(low[x], low[y]); //同时尝试更改low[x];

		}

		else

			if (zzz[y]>0) //如果访问过这个出度。就查看其是否在栈中

			{

				low[x] = min(low[x], dfn[y]); //如果在栈中就用其df序改变low[x];

			}

		temp = next[temp];//尝试找下一个出度。

	}

	if (low[x] == dfn[x]) //如果low[x]和x的df序相同。则弹出栈顶元素到x这个元素，表示

		pop(x); //它们缩点后属于同一个点。

}

void get_ans()

{

	stack[0] = 0; //一开始栈为空。

	memset(flag, false, sizeof(flag)); //一开始所有的节点都没有访问过。

	for (int i = 1; i <= n; i++)

		if (!flag[i]) //没有访问则访问它。

			tarjan(i);

}

int cmp(const bian &a, const bian &b) //则是为sort写的比较函数。

{

	if (a.x < b.x) //x要递增

		return 1;

	if (a.x == b.x && a.y < b.y) //x相同则y也要递增。

		return 1;

	return 0;

}

void output_ans() //输出答案

{

	for (int i = 1; i <= m; i++) //对于每一条边判断其两个端点的新的编号是否相同。

	{ //不同则为重要路径。

		if (bianhao[a[i].x] != bianhao[a[i].y])

			printf("%d %d\n", a[i].x, a[i].y);

	}

}

int main()

{

	input_data();

	get_ans();

	std::sort(a + 1, a + 1 + m, cmp);

	output_ans();

	return 0;

}

巴特西