记录编号	89988	评测结果	AAAAAAAAAA
题目名称	[Ural 1557] 网络攻击	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.315 s
提交时间	2014-03-04 22:42:50	内存使用	31.19 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
const int SIZEN=2010;
vector<int> c[SIZEN];
int N,M;
int numbridge=0,ans=0;
int backedge[SIZEN][SIZEN]={0};//i的子树到某个深度的回边数
int backpref[SIZEN][SIZEN]={0};//i的子树到某个深度(及以下)的回边数
int depth[SIZEN]={0};
int father[SIZEN]={0};
bool visit[SIZEN]={0};
int ufs[SIZEN]={0};
int grand(int x){return ufs[x]==x?x:ufs[x]=grand(ufs[x]);}
void DFS(int x,int dep,int fa){
	depth[x]=dep;
	father[x]=fa;
	visit[x]=true;
	ufs[x]=x;
	for(int i=0;i<c[x].size();i++){
		if(visit[c[x][i]]){
			if(depth[c[x][i]]<depth[x]) backedge[x][depth[c[x][i]]]++;
			continue;
		}
		DFS(c[x][i],dep+1,x);
		for(int j=1;j<depth[x];j++) backedge[x][j]+=backedge[c[x][i]][j];
		if(backpref[c[x][i]][depth[x]]==0) numbridge++;
		else if(backpref[c[x][i]][depth[x]]==1) ans++;//断开一条树边和一条回边,它们都不是桥
		ufs[grand(c[x][i])]=x;
	}
	backedge[x][depth[x]-1]--;//连接它和父亲的边不是回边
	for(int i=1;i<depth[x];i++) backpref[x][i]=backpref[x][i-1]+backedge[x][i];
	if(x!=1){
		for(int i=1;i<=N;i++){
			if(i==x) continue;
			if(grand(i)!=x) continue;//过滤非子树边(这个方法真是略吊......)
			if(!backpref[i][depth[i]-1]) continue;//过滤桥
			if(backpref[x][depth[x]-1]==backpref[i][depth[x]-1]&&backpref[i][depth[i]-1]==backpref[i][depth[x]-1]){
				//断开x的父亲边以及i的父亲边,条件是i的子树不能连到(x的子树除去i的子树),后者亦不能与x的祖先相连
				ans++;
			}
		}
	}
}
void read(void){
	scanf("%d%d",&N,&M);
	int a,b;
	for(int i=1;i<=M;i++){
		scanf("%d%d",&a,&b);
		c[a].push_back(b);
		c[b].push_back(a);
	}
}
int main(){
	freopen("networkattack.in","r",stdin);
	freopen("networkattack.out","w",stdout);
	read();
	DFS(1,1,0);
	ans+=numbridge*(M-numbridge)+numbridge*(numbridge-1)/2;//断开一条桥边和另外一条随便什么边
	printf("%d\n",ans);
	return 0;
}