ZOJ2588 Burning Bridges 无向图的割边

题目大意：求无向图的割边编号。

割边定义：在一个连通图中，如果删去一个边e，图便变成不连通的两个部分，则e为该图的割边。

求法：边(u,v) 不是割边，当且仅当边(u,v)在一个环内。因此所有不在环内的边就是割边，我们要找到它。对图进行Dfs，对每个节点盖上时间戳DfsN，Dfs的方式形成了一棵搜索树。不在环内的边一定在搜索树中（证明：假设不在环内边e不在搜索树中，则Dfs时要访问该边的to点就会经过另外一条边e'。Dfs的出发点是相同的，因此必然e,e'在一个环内），我们要找到它。如果边(u,v)(u->DfsN < v->DfsN)在一个环内，则v的子树中必然存在一节点a与u的祖先节点（包括u）用一个子树外的边相连（与a相连的每一条树外边的to点b都是v的祖先。证明：如果不是，在Dfs时，要么在站在v上向下搜索时把b纳为v的子树，要么在站在b上向下搜索时把v纳为v'的子树）。定义满足该条件的祖先节点们中DfsN最小的节点的DfsN值为u->Low，如果u->DfsN < v->Low，则边(u,v)是割边。易得：u->Low=min{u->DfsN, each v∈u的子节点且未被访问{v->Low}，each e∈v树外边{e->To->DfsN}}。

特判：选边向下遍历时，如果e==曾经到达u的边的反向边，则跳过。因为两条边实际上是一条边。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int MAX_NODE = 10010, MAX_EDGE = 100010 * 2;

struct Node;

struct Edge;

struct Node

{

	int Id, DfsN, Low;

	Edge *Head;

}_nodes[MAX_NODE], *Root;

int _vCount, DfsCnt;

struct Edge

{

	Node *From, *To;

	Edge *Next, *Rev;

	bool IsCut;

	Edge(){}

	Edge(Node *from, Node *to, Edge *next)

		:From(from),To(to),Next(next),IsCut(false){}

}*_edges[MAX_EDGE];

int _eCount;

void Init(int vCount)

{

	Root = 1 + _nodes;

	_vCount = vCount;

	_eCount = 0;

	DfsCnt = 0;

	memset(_nodes, 0, sizeof(_nodes));

}

Edge *NewEdge()

{

	_eCount++;

	return _edges[_eCount] ? _edges[_eCount] : _edges[_eCount] = new Edge();

}

Edge *AddEdge(Node *from, Node *to)

{

	Edge *e = NewEdge();

	e->From = from;

	e->To = to;

	e->Next = from->Head;

	e->IsCut = false;

	from->Head = e;

	return e;

}

void Build(int uId, int vId)

{

	Node *u = uId + _nodes, *v = vId + _nodes;

	u->Id = uId;

	v->Id = vId;

	Edge *e1 = AddEdge(u, v), *e2 = AddEdge(v, u);

	e1->Rev = e2;

	e2->Rev = e1;

}

void Dfs(Node *u, Edge *prev)

{

	u->DfsN = ++DfsCnt;

	u->Low = u->DfsN;

	for (Edge *e = u->Head; e; e = e->Next)

	{

		if (!e->To->DfsN)

		{

			Dfs(e->To, e);

			u->Low = min(u->Low, e->To->Low);

			if (u->DfsN < e->To->Low)

				e->IsCut = e->Rev->IsCut = true;

		}

		else if (prev && e != prev->Rev)

			u->Low = min(u->Low, e->To->DfsN);

	}

}

int main()

{

#ifdef _DEBUG

	freopen("c:\\noi\\source\\input.txt", "r", stdin);

#endif

	int testCase, totNode, totEdge, uId, vId;

	scanf("%d", &testCase);

	while (testCase--)

	{

		scanf("%d%d", &totNode, &totEdge);

		Init(totNode);

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

		{

			scanf("%d%d", &uId, &vId);

			Build(uId, vId);

		}

		Dfs(Root, NULL);

		int ans[MAX_EDGE / 2 + 1], pAns = 0;

		for (int i = 1; i <= _eCount; i+=2)

			if (_edges[i]->IsCut)

				ans[++pAns] = i;

		printf("%d\n", pAns);

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

			printf("%d ", (ans[i]+1)/2);

		if(pAns)

			printf("%d\n", (ans[pAns] + 1) / 2);

		if (testCase)

			printf("\n");

	}

	return 0;

}

巴特西

ZOJ2588 Burning Bridges 无向图的割边

最新文章

热门文章