记录编号	254050	评测结果	AAAAAAAAAA
题目名称	[HAOI 2016]食物链	最终得分	100
用户昵称	Rapiz	是否通过	通过
代码语言	C++	运行时间	0.833 s
提交时间	2016-04-24 15:09:41	内存使用	6.13 MiB

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXV=100000+1,MAXE=200000+1;
struct EDGE{int u,v;}st[MAXE];
struct PRE{
	int phed[MAXV],pnxt[MAXE];//以v为终点的边的标号head[v]
}pret;
int n,m,sz,head[MAXV],nxt[MAXE],ans,ru[MAXV],chu[MAXV],dp[MAXV],pretable[MAXV];
struct TOPSORT{
	int table[MAXV],sz;//0...(sz-1)n
	bool vis[MAXV];
	TOPSORT(){
		memset(this,0,sizeof(this));
	}
	void init(){
		for(int i=1;i<=n;i++) if(!vis[i]) dfs(i);
		for(int i=0,j=sz-1;i<j;i++,j--) swap(table[i],table[j]);
	}
	void dfs(int u){//考虑节点u 
		vis[u]=1;
		for(int e=head[u];e;e=nxt[e]) if(!vis[st[e].v]) dfs(st[e].v);
		table[sz++]=u;
	}
}tps;
void add(int u,int v){
	st[++sz].u=u;
	st[sz].v=v;
	nxt[sz]=head[u];
	head[u]=sz;//正向记录 
	pret.pnxt[sz]=pret.phed[v];
	pret.phed[v]=sz;//反向记录 
	ru[v]++;
	chu[u]++;
}
/*void dfs(int u,int now){//终点是u的简单路径有now条。 
	 if(!chu[u]) ans+=now;
	 
}*/
int main(){
	freopen("chain_2016.in","r",stdin);
	freopen("chain_2016.out","w",stdout);
	cin>>n>>m;
	int u,v;
	for(int i=1;i<=m;i++) cin>>u>>v,add(u,v);
	tps.init();
	//for(int i=tps.sz-1;i>=0;i--) cout<<tps.table[i]<<endl;
	//for(int i=0;i<tps.sz;i++) cout<<tps.table[i]<<endl; 检验是否翻转成功 
	//dp[v] 终点为v的简单路径的条数 
	 //森林-叶节点的父节点 init 
	for(int i=1;i<=n;i++) if(!ru[i]) for(int e=head[i];e;e=nxt[e]) dp[st[e].v]++;
	//printf("init\n");
	//for(int i=1;i<=n;i++) printf("dp[%d]=%d\n",i,dp[i]);
	//叠加计算 
	//printf("叠加:\n");
	for(int i=1;i<=n;i++) {//tps.table[i]
		int csd=tps.table[i];
		for(int pree=pret.phed[csd];pree;pree=pret.pnxt[pree]) {
			dp[csd]+=dp[st[pree].u];
		}
		//printf("dp[%d]=%d\n",csd,dp[csd]);
	}
	/*
	for(int i=1;i<=n;i++) printf("dp[%d]=%d\n",i,dp[i]);*/
	//for(int i=1;i<=n;i++) ans+=dp[i];
	for(int i=1;i<=n;i++) if(!chu[i]) ans+=dp[i];
	cout<<ans;
}
//文件输入输出！