学步园

题目描述

给出 N 个点，M 条边的有向图，对于每个点 v，求 A(v) 表示从点 v 出发，能到达的编号最大的点。

输入格式

第 1 行，2 个整数 N,M。 接下来 M 行，每行 2 个整数 Ui,Vi，表示边 ⟨Ui,Vi⟩。点用 1,2,...,N 编号。

输出格式

N 个整数 A(1),A(2),...,A(N)。

样例输入

4 3
1 2
2 4
4 3

样例输出

4 4 3 4

数据范围

对于 60% 的数据，1 ≤ N,K ≤ 10^3
对于 100% 的数据，1 ≤ N,M ≤ 10^5。

题解

这道题正着做反着做都可以。

正着做要强连通分量缩点，可是T了一个大数据。可能是我写得有问题。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define MAXN 100002
using namespace std;
int n,m,zz,head[MAXN],cnt,hd[MAXN];
struct bian{int to,nx;} e[MAXN],E[MAXN];
int pre[MAXN],low[MAXN],sccnum[MAXN],ct,scc;
int stack[MAXN],v[MAXN],in[MAXN],top,done[MAXN];
//------------------------------------------------------------------
void insert(int x,int y)
{zz++; e[zz].to=y; e[zz].nx=head[x]; head[x]=zz;}
void init()
{
	scanf("%d%d",&n,&m);
	int i,x,y;
	for(i=1;i<=m;i++)
	   {scanf("%d%d",&x,&y);
	    insert(x,y);
	   }
}
//----------------------------------------------------------------------------
void dfs(int x)
{
	pre[x]=low[x]=++ct;
	stack[++top]=x;
	int i,p;
	for(i=head[x];i;i=e[i].nx)
	   {p=e[i].to;
		if(!pre[p]) {dfs(p); low[x]=min(low[x],low[p]);}
		else if(!sccnum[p]) low[x]=min(low[x],pre[p]);
	   }
	p=-1;
	if(low[x]==pre[x])
	   {scc++;
		while(p!=x)
	       {p=stack[top]; top--;
		    sccnum[p]=scc; v[scc]=max(v[scc],p);
		   }
	   }
}
void tarjan()
{
	int i;
	for(i=1;i<=n;i++)
	   {if(!pre[i]) dfs(i);}
	//for(i=1;i<=n;i++) printf("%d ",sccnum[i]);
	//printf("\n");
	//system("pause");
}
void rebuild()
{
	int x,i,p;
	for(x=1;x<=n;x++)
	for(i=head[x];i;i=e[i].nx)
	   {p=e[i].to;
		if(sccnum[x]!=sccnum[p])
		   {cnt++; E[cnt].to=sccnum[p]; E[cnt].nx=hd[sccnum[x]]; hd[sccnum[x]]=cnt;
		    in[sccnum[p]]++;
		   }
	   }
	//for(i=1;i<=scc;i++) printf("%d ",in[i]);
	//printf("\n");
	//system("pause");
}
//------------------------------------------------------------------------------
void find(int x)
{
	if(done[x]) return;
	int i,p;
	done[x]=1;
	for(i=hd[x];i;i=E[i].nx)
	   {p=E[i].to;
	    find(p);
	    v[x]=max(v[x],v[p]);
	   }
}
void work()
{
	int i;
	for(i=1;i<=scc;i++)
	   {if(in[i]==0) find(i);}
	for(i=1;i<=n;i++)
	   {printf("%d",v[sccnum[i]]);
	    if(i<n) printf(" ");
	    else printf("\n");
	   }
}
int main()
{
	freopen("graph.in","r",stdin);
	freopen("graph.out","w",stdout);
	init(); tarjan();
	rebuild(); work();
	return 0;
}

反着做只要保证每个点走一次即可。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define MAXN 100002
using namespace std;
int n,m,zz,head[MAXN];
struct bian{int to,nx;} e[MAXN];
int ans[MAXN],done[MAXN];
void insert(int x,int y)
{zz++; e[zz].to=y; e[zz].nx=head[x]; head[x]=zz;}
void init()
{
	scanf("%d%d",&n,&m);
	int i,x,y;
	for(i=1;i<=m;i++)
	   {scanf("%d%d",&x,&y);
	    insert(y,x);
	   }
}
void dfs(int x)
{
	if(done[x]) return;
	int i,p;
	done[x]=1;
	for(i=head[x];i;i=e[i].nx)
	   {p=e[i].to;
		if (!done[p])
	       {ans[p]=max(ans[p],ans[x]);
		    dfs(p);
		   }
	   }
}
void work()
{
	int i;
	for(i=n;i>=1;i--) ans[i]=i;
	for(i=n;i>=1;i--) dfs(i);
	for(i=1;i<=n;i++) printf("%d ",ans[i]);
}
int main()
{
	freopen("graph.in","r",stdin);
	freopen("graph.out","w",stdout);
	init(); work();
	return 0;
}