URAL/1557

来自"NOCOW"

又是yezi的代码哦~题解见2008曹钦翔的论文吧~

#include <cstdio>
int n, m, e[200001], head[2001] = {0}, next[200001];
int ans1, r, q[2001], p[2001], s[2001], t[2001], d[2001], l[2001][2001] = {0};
long long ans2;
void add (int k, int x, int y)
{
	e[k] = y;
	next[k] = head[x];
	head[x] = k;
}
void init ()
{
	int i, x, y;
	scanf ("%d%d", &n, &m);
	for (i = 1; i <= m; i++)
	{
		scanf ("%d%d", &x, &y);
		if (x != y)
		{
			add (i, x, y);
			add (m + i, y, x);
		}
	}
}
void dfs (int k, int fa)
{
	int i, x, pos = ++r;
	q[r] = k;
	p[k] = 0; d[k] = d[fa] + 1;
	for (x = head[k]; x; x = next[x])
		if (e[x] == fa)
			p[k]++;
		else if (d[e[x]] && d[e[x]] < d[k])
			l[k][d[e[x]]]++;
		else if (!d[e[x]])
		{
			dfs (e[x], k);
			for (i = 1; i < d[k]; i++)
				l[k][i] += l[e[x]][i];
		}
	s[k] = p[k];
	for (i = 1; i < d[k]; i++)
		if (l[k][i])
			s[k] += l[k][i], t[k] = i;
	if (s[k] == 1)  ans1++;
	else
	{
		if (s[k] == 2)  ans2++;
		if (p[k] > 1) return;
		for (i = pos + 1; i <= r; i++)
			if (p[q[i]] == 1 && s[k] == s[q[i]] && t[q[i]] < d[k])
				ans2++;
	}
}
int main ()
{
	init ();
	ans1 = ans2 = 0;
	r = 0; d[0] = 0;
	dfs (1, 0);
	ans2 += ans1 * (m - ans1) + ans1 * (ans1 - 1) / 2;
	printf ("%I64d\n", ans2);
	return 0;
}