Codeforces Beta Round #89 (Div. 2) E. Bertown roads（Tarjan、边双连通分量）

题目链接：http://codeforces.com/problemset/problem/118/E

思路：首先要判断图是否是边双连通，这个Tarjan算法可以判断，若low[v] > dfn[u],则说明边（u，v)是桥，从而这个图不是边双连通，然后发现在判断的时候已经访问了所有的顶点，顺便加入就可以了。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#include <stack>

#include <queue>

#include <map>

#define REP(i, a, b) for (int i = (a); i < (b); ++i)

#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)

using namespace std;

const int MAX_N = (300000 + 100);

int N, M, cnt, bcc_count;

int low[MAX_N], dfn[MAX_N], vis[MAX_N], mark[MAX_N];

stack<int > S;

vector<int > g[MAX_N];

map<pair<int, int>, int> mp;

vector<pair<int, int > > edge;

bool Tarjan(int u, int fa)

{

	int tag = 0;

	low[u] = dfn[u] = ++cnt;

	vis[u] = 1;

	S.push(u);

	REP(i, 0, (int)g[u].size()) {

		int v = g[u][i];

		if (v == fa && !tag) { tag = 1;  continue; }

		if (!dfn[v]) {

			if (!Tarjan(v, u)) return false;

			low[u] = min(low[u], low[v]);

			if (low[v] > dfn[u]) return false;

			else {

				pair<int, int >PPI = make_pair(u, v);

				edge.push_back(PPI);

				mark[mp[PPI]] = 1;

			}

		}

		else if (vis[v]) {

			low[u] = min(low[u], dfn[v]);

			pair<int, int> PPI = make_pair(u, v);

			if (!mark[mp[PPI]]) {

				mark[mp[PPI]] = 1;

				edge.push_back(PPI);

			}

		}

	}

	return true;

}

int main()

{

	cin >> N >> M;

	FOR(i, 1, M) {

		int u, v; cin >> u >> v;

		g[u].push_back(v);

		g[v].push_back(u);

		mp[make_pair(u, v)] = i;

		mp[make_pair(v, u)] = i;

	}

	cnt = bcc_count = 0;

	memset(vis, 0, sizeof(vis));

	memset(mark, 0, sizeof(mark));

	memset(dfn, 0, sizeof(dfn));

	if (!Tarjan(1, -1)) { puts("0"); return 0; }

	REP(i, 0, (int)edge.size()) {

		printf("%d %d\n", edge[i].first, edge[i].second);

	}

	return 0;

}