蒟蒻发问
查看原帖
蒟蒻发问
1031797
2010126zhy楼主2024/10/19 11:38
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int>g[N];

int d[N],n;
int dfs(int x){
	if(d[x]>0)return d[x];
	d[x]=x;
	for(int i=1;i<=g[x].size();i++)
	{
		int v=g[x][i];
		if(!d[v])d[x]=max(d[x],dfs(v));
		else d[x]=max(d[x],d[v]);
	}
	return d[x];
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int n,m,x,y;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		g[x].push_back(y);
	}
	for(int i=n;i>=1;i--){
		if(!d[x])dfs(i);
		else d[i]=max(d[i],i);
	}
	for(int i=1;i<=n;i++)cout<<d[i]<<" ";
	
	return 0;
}
2024/10/19 11:38
加载中...