记录编号	254404	评测结果	AAAAAAAAAA
题目名称	[HAOI 2016]食物链	最终得分	100
用户昵称	甘罗	是否通过	通过
代码语言	C++	运行时间	0.299 s
提交时间	2016-04-25 13:33:14	内存使用	10.23 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
using namespace std;

int n,m,i,bh,cnt,tt,j;
long long ans;
int a[200010],a2[200010],b[200010],b2[200010];
int rd[100010],l[100010],r[100010];
int t[100010][5];
int z[1000010];

void gb(int low,int high){
	int q=0,w=0,e=0,mid=0,k=0;
	if (low==high) return;
	mid=(low+high)/2;
	gb(low,mid); gb(mid+1,high);
	q=low; w=mid+1; e=low;
	while (q<=mid&&w<=high) {
		if (a[q]<=a[w]) {
			a2[e]=a[q];
			b2[e]=b[q];
			e++; q++;
		} else
		 {
		 	a2[e]=a[w];
		 	b2[e]=b[w];
		 	e++; w++;
		 }
	}
	if (q<=mid) 
		while (q<=mid) {
			a2[e]=a[q];
			b2[e]=b[q];
			e++; q++;
		} else 
		while (w<=high) {
			a2[e]=a[w];
			b2[e]=b[w];
			e++; w++;
		}
		
	for (k=low;k<=high;k++){
	a[k]=a2[k];
	b[k]=b2[k];
	}
	
	return;
} 

int main(){
	freopen("chain_2016.in","r",stdin);
	freopen("chain_2016.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<=m;i++)
	{
		scanf("%d%d",&a[i],&b[i]);
		rd[b[i]]++;
	}
	gb(1,m);
	
	bh=a[1];
	t[bh][1]=1;
	
	for (i=2;i<=m;i++)
	if (bh!=a[i]) {
		t[bh][2]=i-1; bh=a[i]; t[bh][1]=i;
	}
	t[bh][2]=m;
	
	cnt=0;
	
	for (i=1;i<=n;i++)
	if (rd[i]==0) {
		if (t[i][1]!=0) {  //   我自己都没注意我加了特判！！！ 
			r[0]++;
			r[r[0]]=i;
		}
	}
	
	for (i=1;i<=r[0];i++)
	{
		cnt++;
		z[cnt]=r[i];
		tt=cnt;
		while (z[tt]!=0) {
		for (j=t[z[tt]][1];j<=t[z[tt]][2];j++)
		{
			rd[b[j]]--;
			if (rd[b[j]]==0) {
				cnt++; z[cnt]=b[j];
			}
		
		}
		tt++;
		}	
	}
	
	for (i=1;i<=r[0];i++)
	l[r[i]]=1;
	
	for (i=1;i<=n;i++)
	if (t[z[i]][1]!=0) 
	for (j=t[z[i]][1];j<=t[z[i]][2];j++)
	l[b[j]]=l[b[j]]+l[z[i]];
	
	for (i=1;i<=n;i++)
	if (t[i][1]==0) ans+=l[i];
	cout<<ans<<endl;
	
	return 0;
}