Graph_Master(连通分量_A_双连通分量+桥)

hdu 5409

题目大意：给出一张简单图，求对应输入的m条边，第i-th条边被删除后，哪两个点不连通(u,v，u<v)，若有多解，使得u尽量大的同时v尽量小。

解题过程：拿到题面的第一反应缩点，然后就没有然后了，因为输出的奇葩要求，确实是没有想到，而且之前tarjan面对的是有向图，而这题是无向图，显然没有强连通分量（百度后得知：有向图叫作强连通，无向图称为双连通，有点双，边双之分，此题是边双），加之这题的神奇输出，就算要求任意解，笔者也不会写，于是纠结了大半小时，就题解走起来。

题解：无向图的边双连通分量缩点+桥，什么是边双连通图？即一张图任意两点都可以通过至少两条路径到达，即路径没有公共边（点双即没有公共点）。什么叫桥？就是一条边，一条如果被移除了，双连通分量个数增加（双连通图必无桥）的边。那么问题就来了，找桥。笔者会啊，找桥就是tarjan的low和dfn比，那么问题又来了，输出怎么办？题解说道：如果被移除的边即是桥，必有两个分量，一个含有第n个点，一个不含，于是乎，不妨设mx[u]与mx[v]为e<u,v>为桥时，两端分量的最大点编号(mx[u]本应为以u为根的结点中最大编号，但是是无向图，所以可以看作就是连通分量的最大编号)，可知答案为min(mx[u],mx[v]), min(mx[u],mx[v])+1 ' ' ，为什么？因为含n的分量如果是答案，那答案就是n, n+1，这个显然不符合题目n个结点的说明，故而答案为上述min, min+1。

实现技巧：可以利用tarjan就是完成双连通的查找来处理桥(tarjan的low[]与dfn[])和mx(tarjan的深搜特性)。其实这题笔者更想称之为边双连通分量+桥。

---

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#define CLR(a) memset((a),0,sizeof(a))
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 1e5 + 16;
struct Edge
{
	int nxt, u, v;
};
Edge edge[N<<1];
int ecnt, head[N];
int dfn[N], mx[N], low[N];
int dep;
bool isbridge[N<<1];
int n, m;

void _add( int _u, int _v )
{
	edge[ecnt].u = _u;
	edge[ecnt].v = _v;
	edge[ecnt].nxt = head[_u];
	head[_u] = ecnt++;
}

int tarjan( int u, int pr )
{
	low[u] = dfn[u] = ++dep;
	mx[u] = u;
	
	for ( int i = head[u]; i+1; i = edge[i].nxt )
	{
		int v = edge[i].v;
		if ( v == pr ) continue;
		if ( !dfn[v] ) mx[u] = max( mx[u], tarjan(v,u) );
		low[u] = min( low[u], low[v] );
		if ( low[v] > dfn[u] ) isbridge[i>>1] = 1;`// the i-th edge is bridge.
	}
	return mx[u];
}

void bridge()
{
	for ( int i = n; i >= 1; i -- )
		if ( !dfn[i] ) tarjan(i,-1);
        //tarjan(n,-1); // it can also get accepted, but it's not so rigorous as i see.
	
	for ( int i = 0; i < m; i ++ )
	{
		if ( !isbridge[i] )
		{
			puts("0 0");
			continue;
		}
		int _u = edge[i<<1].u, _v = edge[i<<1].v;`// the original order of e<u,v>
		if ( dfn[_u] > dfn[_v] )
			printf("%d %d
", mx[_u], mx[_u]+1);
		else printf("%d %d
", mx[_v], mx[_v]+1);
	}
}

void init()
{
	CLR(dfn), CLR(mx), CLR(low), CLR(isbridge);
	memset(head,-1,sizeof(head));
	ecnt = dep = 0;
}

int main()
{
	int T;
	scanf("%d", &T);
	while ( T -- )
	{
		init();
		scanf("%d%d", &n, &m);
		for ( int i = 0; i < m; i ++ )
		{
			int u, v;
			scanf("%d%d", &u, &v);
			_add(u,v);
			_add(v,u);
		}
		bridge();
	}
	return 0;
}