HDU1269 有向图强连通分量

题目大意：问一个有向图是否任意两点在两个方向上互相连通。

有向图强连通分量定义：如果一个图中的任意两点在两个方向上都互相连通，则该图为强连通图。极大强连通图为有向图的强连通分量（注意是极大，不是最大。一个图会有多个强连通分量）。感性理解，强连通图就是多个环，或者一个点连接在一起所产生的图。

如何求？定义节点cur->Low，cur的子搜索树节点a中如果存在边（a，b），使得b->DfsN小于cur->DfsN，则cur->Low=min foreach b{b->DfsN}，否则为cur->DfsN。显然，cur->Low所对应的节点位于cur所在极大强连通分量中，且是cur所在环中深度最浅的。

新定义一个栈维护一组节点，其使得处理完栈内节点cur以上的节点后，cur以上节点的Low <= cur->Low（它们位于cur子搜索树中的各个枝杈上（而不仅仅存在于一个枝杈中，这是系统栈所做不到的），不存在满足该条件却不在该栈内的节点），即cur及以上节点在一个强连通分量内。如果cur->Low == cur->DfsN，则cur是其所在强连通分量中深度最浅的，再往栈下面走的节点就不属于这个连通分量了，此时便可以输出连通分量，然后将cur及以上节点全部弹出。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

const int MAX_NODE = 10010, MAX_EDGE = 100010;

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;

	Edge() {}

}*_edges[MAX_EDGE];

int _eCount;

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;

	from->Head = e;

	return e;

}

vector<Node*> Stack;

void Init(int vCount)

{

	_vCount = vCount;

	_eCount = 0;

	DfsCnt = 0;

	Root = 1 + _nodes;

	Stack.clear();

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

}

void Dfs(Node *cur)

{

	cur->DfsN = cur->Low = ++DfsCnt;

	Stack.push_back(cur);

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

	{

		if (!e->To->DfsN)

		{

			Dfs(e->To);

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

		}

		else

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

	}

	if (cur != Root && cur->Low == cur->DfsN)

	{

		while (Stack.back() != cur)

			Stack.pop_back();

		Stack.pop_back();

	}

}

int main()

{

#ifdef _DEBUG

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

	freopen("c:\\noi\\source\\output.txt", "w", stdout);

#endif

	int totNode, totEdge, uId, vId;

	while (scanf("%d%d", &totNode, &totEdge) && (totNode || totEdge))

	{

		Init(totNode);

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

		{

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

			_nodes[uId].Id = uId;

			_nodes[vId].Id = vId;

			AddEdge(uId + _nodes, vId + _nodes);

		}

		Dfs(Root);

		if (Stack.size()!=totNode)

			printf("No\n");

		else

			printf("Yes\n");

	}

	return 0;

}

巴特西

HDU1269 有向图强连通分量

最新文章

热门文章