90分,#8超时,求大佬优化
查看原帖
90分,#8超时,求大佬优化
772478
Wisdom_chicken_god楼主2023/7/18 14:09
#include<bits/stdc++.h>
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int n,m,maxi;
struct Edge
{
	int next;
	int to;
}edge[100001];
int h[100001],num,b[100001];
void add(int fr,int to)
{
	edge[++num].next=h[fr];
	edge[num].to=to;
	h[fr]=num;
}
void dfs(int x){
	maxi=max(maxi,x);
	b[x]=1;
	for(int i=h[x];i;i=edge[i].next)
	{
		int y=edge[i].to;
		if(b[y])
		continue;
		dfs(y);
		maxi=max(maxi,y);
	}
}
int main(){
	n=read();
	m=read();
	for(int i=1;i<=m;i++){
		int f,t;
		f=read();
		t=read();
		add(f,t);
	}
	for(int i=1;i<=n;i++){
		memset(b,0,sizeof(b));
		dfs(i);
		printf("%d ",maxi);
		maxi=0;
	}
	return 0;
}
2023/7/18 14:09
加载中...