WA on #7

评测记录

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<cmath>
#include<stack>
#define N 100005
#define M 100005
using namespace std;
int n,m,cnt,dfs,scs;
int nex[M],fir[N],poi[M],rot[N],a[N],dfn[N],val[N],low[N],bok[N],in[N];
stack<int>s;
vector<int>scc[N],edge[M];
map<int,bool>vis;
int re()
{
	int x=0,p=1;
	char y=getchar();
	for(;y>'9'||y<'0';y=getchar())
		if(y=='-')
			p=-p;
	for(;y>='0'&&y<='9';y=getchar())
		x=x*10+y-'0';
	return x*p;
}
void wr(int x)
{
	if(x<0)
		putchar('-'),x=-x;
	if(x>9)
		wr(x/10);
	putchar(x%10+'0');
}
void ins(int x,int y)
{
	nex[++cnt]=fir[x];
	poi[cnt]=y;
	fir[x]=cnt;
}
void Tarjan(int x)
{
	dfn[x]=low[x]=++dfs;
	bok[x]=1,s.push(x);
	for(int i=fir[x];i;i=nex[i])
	{
		int p=poi[i];
		if(!dfn[p])
			Tarjan(p),low[x]=min(low[x],low[p]);
		else if(bok[p])
			low[x]=min(low[x],dfn[p]);
	}
	if(dfn[x]==low[x])
		for(scs++;s.size();)
		{
			int ls=s.top();
			s.pop(),bok[ls]=0;
			val[scs]=max(val[scs],ls);
			rot[ls]=scs,scc[scs].push_back(ls);
			if(ls==x)
				break;
		}
}
void dfss(int x)
{
	if(bok[x])
		return;
	bok[x]=1;
	a[x]=max(a[x],val[x]);
	for(int j=0,l=edge[x].size();j<l;j++)
	{
		int p=edge[x][j];
		if(!bok[p])
			dfss(p);
		a[x]=max(a[x],a[p]);
	}
}
signed main()
{
	n=re(),m=re();
	for(int i=1;i<=m;i++)
	{
		int u=re(),v=re();
		ins(u,v);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			Tarjan(i);
	for(int k=1;k<=scs;k++)
		for(int j=0,l=scc[k].size();j<l;j++)
		{
			int x=scc[k][j];
			for(int i=fir[x];i;i=nex[i])
			{
				int p=poi[i];
				if(rot[p]==k)
					continue;
				if(vis[k*13331+rot[p]])
					continue;
				vis[k*13331+rot[p]]=1;
				edge[k].push_back(rot[p]);
				in[rot[p]]++;
			}
		}
	memset(bok,0,sizeof(bok));
	for(int i=1;i<=scs;i++)
		if(!in[i])
			dfss(i);
	for(int i=1;i<=n;i++)
		wr(a[rot[i]]),putchar(' ');
	return 0;
}