HDU [P3849]

tarjan 求 无向图的割边 (桥)

边 (x,y) 是桥当且仅当, 对于 x 的子节点 y ,low[x] < dfn[y]

对于连向父节点的边要特殊处理

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <string>

#pragma comment(linker, "/STACK:16777216")

#include <map>

using namespace std;

const int MAXN = 10005, MAXM = 200005;

int head[MAXN], nume, n, m, dfn[MAXN], low[MAXN], ind, cnt, T, tot;

map <string, int> Hash;

string s[MAXN];

bool f[MAXM];

struct edge{

	int to, nxt;

}e[MAXM];

void adde(int from, int to) {

	e[++nume].to = to;

	e[nume].nxt = head[from];

	head[from] = nume;

}

void tarjan(int u, int id) {

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

	for(int i = head[u]; i; i = e[i].nxt) {

		int v = e[i].to;

		if(!dfn[v]) {

			tarjan(v, i);

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

			if(low[v] > dfn[u]) {

				f[i] = f[((i - 1) ^ 1) + 1] = 1;

			}

		}else if(i != ((id - 1) ^ 1) + 1) low[u] = min(low[u], dfn[v]);

	}

}

int main() {

	cin >> T;

	while(T--) {

		cin >> n >> m;

		memset(head, 0, sizeof(head));

		memset(f, 0, sizeof(f));

		nume = ind = tot = cnt = 0;

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

		memset(low, 0, sizeof(low));

		Hash.clear();

		for(int i = 1; i <= m; i++) {

			string s1, s2;

			cin >> s1 >> s2;

			int u = Hash[s1];

			if(!u) u = ++tot, s[u] = s1;

			Hash[s1] = u;

			int v = Hash[s2];

			if(!v) v = ++tot; s[v] = s2;

			Hash[s2] = v;

			adde(u, v); adde(v, u);

		}

		tarjan(1, 0);

		int fff = 1;

		for(int i = 1; i <= tot; i++) if(!dfn[i]) {fff = 0;break;}

		if(!fff) {

			printf("0\n"); continue;

		}

		for(int i = 1; i <= nume; i++) if(f[i]) cnt++;

		cnt /= 2;

		cout << cnt << endl;

		for(int i = 1; i < nume; i += 2) {

			if(f[i]) cout << s[e[((i - 1) ^ 1) + 1].to] << " " << s[e[i].to] << endl;

		}

	}

}