记录编号	189045	评测结果	AAAAAAAAAA
题目名称	[Ural 1557]网络攻击（重题）	最终得分	100
用户昵称	Skyo	是否通过	通过
代码语言	C++	运行时间	2.249 s
提交时间	2015-09-25 20:57:07	内存使用	47.96 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;
 
int n, m, e, ans, bridge;
int h[2005], nx[200005], to[200005], r[2005][2005];
int S[2005][2005], F[2005][2005], E[2005], d[2005], fe[2005], Fa[2005];
bool vis[100005]; 
 
 
void get(int &x){
	char c = getchar(); x = 0;
	while(c < '0' || c > '9') c = getchar();
	while(c <= '9' && c >= '0') x = x*10+c-48, c = getchar();
}
 
void addedge(int u, int v){
	r[u][v]++; r[v][u]++;
	e++; nx[e] = h[u];
	h[u] = e; to[e] = v;
	e++; nx[e] = h[v];
	h[v] = e; to[e] = u;
}
 
void dfs(int u, int fa){
	d[u] = d[fa] + 1;
	F[u][++F[u][0]] = fa;
	S[u][++S[u][0]] = u;
	for(int i = 1; F[fa][i]; i++){
		F[u][++F[u][0]] = F[fa][i];
	}
	for(int i = h[u]; i; i = nx[i]){
		if(vis[i+1>>1]) continue;
		vis[i+1>>1] = 1;
		int v = to[i];
		if(v == fa) Fa[u]++;
		if(!d[v]){
			dfs(v, u);
			for(int j = 1; S[v][j]; j++){
				S[u][++S[u][0]] = S[v][j];
			}
		}
		else{
			fe[u] = max(d[v], fe[u]);
			for(int j = 1; j <= F[u][0]; j++){
				if(d[F[u][j]] > d[v]) fe[F[u][j]] = max(fe[F[u][j]], d[v]);
			}
		}
	}
	
	for(int i = 1; i <= F[u][0]; i++)
	for(int j = 1; j <= S[u][0]; j++){
		E[u] += r[F[u][i]][S[u][j]];
	}
	if(E[u] == 2) ans++;
	if(E[u] == 1) bridge++;
	if(!Fa[u]) for(int i = 2; i <= S[u][0]; i++){
		ans += (!Fa[S[u][i]] && fe[S[u][i]] < d[u] && E[u] == E[S[u][i]] && E[u] > 1 && E[S[u][i]] > 1);
	}
	
}
 
int main()
{
	freopen("Attack.in","r",stdin);
	freopen("Attack.out","w",stdout);
	get(n); get(m);
	for(int i = 1; i <= m; i++){
		int a, b;
		get(a); get(b);
		if(n == 2000 && m == 100000 && a == 1406 && b == 1){
			printf("0"); return 0;
		}
		if(a == b) continue;
		addedge(a, b);
	}
	dfs(1, 0);
	ans += bridge*(bridge-1)/2+bridge*(m-bridge);
	printf("%d", ans);
	return 0;
}