Tarjan+Topo......
这份117行的绿题代码招来了9个WA以及一旁机房大佬的不屑
dalao们帮忙看看拜托拜托
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<queue>
using namespace std;
#define signed register int
#define N 1000100
int n,m,num,head[N],head2[N],dfn[N],low[N],sta[N],sta_max[N],in[N],visn,stan,k;//stan 缩点后的序号 in 缩点后每点的入度
bool vis[N];
stack<int>s;
queue<int>q;
struct Edge{
int to;
int next;
}edge[N];
struct Edge2{
int to;
int next;
}edge2[N];//缩点后建立反向边
inline void AddEdge1(int x,int y)
{
edge[++num].to=y;
edge[num].next=head[x];
head[x]=num;
}
inline void AddEdge2(int x,int y)
{
edge2[++num].to=y;
edge2[num].next=head2[x];
head2[x]=num;
}
inline void Tarjan(int u)
{
dfn[u]=low[u]=++visn;
s.push(u);vis[u]=true;
for(signed i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(!vis[v])
{
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(!sta[v])
low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
sta[u]=++stan;
while(s.top()!=u)
{
sta[s.top()]=stan;
sta_max[stan]=max(sta_max[stan],s.top());
s.pop();
}
sta_max[stan]=max(sta_max[stan],s.top());
s.pop();
}
}
inline void Topo()
{
for(signed i=1;i<=stan;i++)
if(!in[i])q.push(i);
while(!q.empty())
{
int fro=q.front();q.pop();
for(signed i=head2[fro];i;i=edge2[i].next)
{
int to=edge2[i].to;
sta_max[to]=max(sta_max[to],sta_max[fro]);
in[to]--;
if(!in[to])q.push(to);
}
}
}
inline void starts()
{
memset(head,0,sizeof(head));
memset(head2,0,sizeof(head));
memset(dfn,0,sizeof(dfn));
memset(vis,false,sizeof(vis));
memset(sta_max,0,sizeof(sta_max));
memset(in,0,sizeof(in));
}//初始化
int main()
{
freopen("P3916.in","r",stdin);
freopen("P3916.out","w",stdout);
ios::sync_with_stdio(false);
starts();
cin>>n>>m;
for(signed i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
AddEdge1(x,y);
}
for(signed i=1;i<=n;i++)
if(!dfn[i])Tarjan(i);
for(signed k=1;k<=n;k++)
{
for(signed i=head[k];i;i=edge[i].next)
{
int to=edge[i].to;
if(sta[k]!=sta[to])
{
AddEdge2(to,k);
in[sta[k]]++;
}
}
}
Topo();
for(signed i=1;i<=n;i++)
cout<<sta_max[sta[i]]<<' ';
return 0;
}
蒟蒻求助