记录编号	402576	评测结果	AAAAAAAAAAAAAAAA
题目名称	膜拜	最终得分	100
用户昵称	test	是否通过	通过
代码语言	C++	运行时间	0.200 s
提交时间	2017-05-06 20:43:02	内存使用	6.14 MiB

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#include<queue>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
int n,m,num,numm,dfn,scc,dis[100500],dis1[100500],sccno[100500],low[100500],pre[100500],tot[100500];
bool pan[100500];
stack <int> s;
struct date{
	int first,nxt,to;
};
date a[100005];
date G1[100005],G2[100005];
int gi(){
	int res=0,w=1;
	char ch=getchar();
	while ((ch>'9' || ch<'0')&&ch!='-') ch=getchar();
	if (ch=='-') w=-1,ch=getchar();
	while (ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
	return res*w;
}
void add(int l,int to){
	a[++num].to=to;
	a[num].nxt=a[l].first;
	a[l].first=num;
}
void ADD(int l,int to){
	G1[++numm].to=to;
    G1[numm].nxt=G1[l].first;
	G1[l].first=numm;
    G2[numm].to=l;
    G2[numm].nxt=G2[to].first;
	G2[to].first=numm;
}
void Tarjan(int x){
	low[x]=pre[x]=++dfn;
	s.push(x);
    for(int i=a[x].first;i;i=a[i].nxt){
		int v=a[i].to;
		if(!pre[v]){
			Tarjan(v);
			low[x]=min(low[x],low[v]);
		} else if(!sccno[v]){
			low[x]=min(low[x],pre[v]);
		}
	}
	if(low[x]==pre[x]){
		++scc;
		for(;;){
			int xx=s.top();
			s.pop();
			sccno[xx]=scc;
			tot[scc]++;
			if(xx==x) break;
		}
	}
}
void point(){
	for(int i=1;i<=n;i++)
		for(int j=a[i].first;j;j=a[j].nxt){
			if(sccno[i]!=sccno[a[j].to])
				ADD(sccno[i],sccno[a[j].to]);
		}
}
void spfa(int k){
	memset(pan,true,sizeof(pan));
	queue <int> ss;
	while(!ss.empty()) ss.pop();
	ss.push(sccno[1]);
	pan[sccno[1]]=false;
	if(k==1) dis[sccno[1]]=tot[sccno[1]];
	if(k==2) dis1[sccno[1]]=tot[sccno[1]];
	while(!ss.empty()){
		register int x=ss.front();
		ss.pop();
		pan[x]=true;
		if(k==1){
			for(int i=G1[x].first;i;i=G1[i].nxt){
				register int to=G1[i].to;
				if(dis[to]<dis[x]+tot[to]){
				   dis[to]=dis[x]+tot[to];
					if(pan[to]){
						pan[to]=false;
						ss.push(to);
					}
				}
			}
		} else{
			for(int i=G2[x].first;i;i=G2[i].nxt){
				int to=G2[i].to;
				if(dis1[to]<dis1[x]+tot[to]){
					dis1[to]=dis1[x]+tot[to];
					if(pan[to]){
						pan[to]=false;
						ss.push(to);
					}
				}
			}
		}
	}
}				
int main()
{
	freopen("OrzOrz.in","r",stdin);
	freopen("OrzOrz.out","w",stdout);
	n=gi(),m=gi();
	for(int i=1;i<=m;i++){
		register int x,y;
		x=gi(),y=gi();
		add(x,y);
	}
	for(int i=1;i<=n;i++)
		if(!pre[i])
			Tarjan(i);
	point();
	spfa(1);
	spfa(2);
	int maxn=0;
	for(int i=1;i<=scc;i++)
		for(int j=G2[i].first;j;j=G2[j].nxt)
			if(dis[i]&&dis1[G2[j].to]) maxn=max(maxn,dis[i]+dis1[G2[j].to]);
	if(maxn==tot[sccno[1]]) printf("%d",maxn);
	else printf("%d",maxn-tot[sccno[1]]);
	return 0;
}