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

题目大意：给出一张简单图，求对应输入的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, 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\n", mx[_u], mx[_u]+1);

		else printf("%d %d\n", 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;

}

巴特西

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

最新文章

热门文章