POJ3177 Redundant Paths 图的边双连通分量

题目大意：问一个图至少加多少边能使该图的边双连通分量成为它本身。

图的边双连通分量为极大的不存在割边的子图。图的边双连通分量之间由割边连接。求法如下：

1. 求出图的割边
2. 在每个边双连通分量内Dfs，标记每个节点所属于的双连通分量编号
3. 构建一新图Tree，一个节点代表一个双连通分量。原图中遍历割边，将割边连接的两个双连通分量在Tree中的对应节点连接。
4. Tree中算出每个节点的度数，如果一节点度数为1，则其为叶子节点。输出（叶子节点数+1/2）。（连接了叶子节点，就形成了环，Tree中不连接叶子节点的边因为在环内，所以不再是割边了。）

注意：如果一个边是割边，则其反向边也是割边。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

#include <cassert>

using namespace std;

#define LOOP(i, n) for(int i=1; i<=n; i++)

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

struct G {

	struct Node;

	struct Edge;

	struct Node {

		int Id, DfsN, Low, InBlock, Degree;

		Edge *Head;

	}_nodes[MAX_NODE], *Root;

	struct Edge {

		bool IsCut;

		Node *From, *To;

		Edge *Next, *Rev;

		Edge(){}

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

	}*_edges[MAX_EDGE];

	int _vCount, _eCount, DfsCnt, BlockCnt, LeafCnt;

	void Init() {

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

		_vCount = _eCount = DfsCnt = LeafCnt = 0;

		BlockCnt = 0;

	}

	Edge *NewEdge() {

		_eCount++;

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

	}

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

		Edge *e = NewEdge();

		*e = Edge(from, to, from->Head);

		from->Head = e;

		return e;

	}

	void Build(int uId, int vId, bool is2d) {

		while (_vCount < uId || _vCount < vId)

			_vCount++;

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

		u->Id = uId;

		v->Id = vId;

		Edge *e1 = AddEdge(u, v);

		if (is2d) {

			Edge *e2 = AddEdge(v, u);

			e1->Rev = e2;

			e2->Rev = e1;

		}

	}

	void FindCutEdge(Node *u, Edge *Prev) {//易忘点：prev

		if (u->DfsN)

			return;

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

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

			if (!e->To->DfsN) {

				FindCutEdge(e->To, e);

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

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

					e->IsCut = e->Rev->IsCut = true;//易忘点：e->Rev->IsCut

			}

			else if (e->Rev != Prev)

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

		}

	}

	void FindCutEdge() {

		LOOP(i, _vCount) {//易忘点：图不一定连通，所以要循环。

			Root = i + _nodes;

			FindCutEdge(Root, NULL);

		}

	}

	void SetBlock(Node *u) {

		u->InBlock = BlockCnt;

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

			if (!e->IsCut && !e->To->InBlock)

				SetBlock(e->To);

	}

	void SetBlock() {

		LOOP(i, _vCount) {

			if (!_nodes[i].InBlock) {

				BlockCnt++;

				SetBlock(i + _nodes);

			}

		}

	}

	void SetLeafCnt() {//此处比较有技巧，注意看看

		LOOP(i, _eCount)

			_edges[i]->To->Degree++;

		LOOP(i, _vCount)

			if (_nodes[i].Degree <= 1)

				LeafCnt++;

	}

}Org, Tree;

int main() {

#ifdef _DEBUG

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

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

#endif

	Org.Init();

	Tree.Init();

	int totNode, totEdge, uId, vId;

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

	LOOP(i, totEdge) {

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

		Org.Build(uId, vId, true);

	}

	Org.FindCutEdge();

	Org.SetBlock();

	LOOP(i, Org._eCount)

		if (Org._edges[i]->IsCut)

			Tree.Build(Org._edges[i]->From->InBlock, Org._edges[i]->To->InBlock, false);

	Tree.SetLeafCnt();

	printf("%d\n", (Tree.LeafCnt + 1) / 2);

	return 0;

}