dfs90分求调
查看原帖
dfs90分求调
1447441
zhang46楼主2025/1/22 14:54

反向建图了,但还是在第8个点TLE

#include<bits/stdc++.h>
using namespace std;
int n,m,k=0,h=0,ans[200002];
struct line{
	int to,pre,w;
};
line b[200002];
int head[200002];
bool vis[200002];
void adg(int x,int y){
	k++;
	b[k].pre=head[x];
	b[k].to=y;
	head[x]=k;
}
void dfs(int x,int y){
	if(!ans[y]){
		ans[y]=x;
		h++;
	}
	if(h==n)return;
	for(int i=head[y];i;i=b[i].pre){
		int z=b[i].to;
		if(vis[z])continue;
		vis[z]=1;
		dfs(x,z);
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		adg(y,x);
	}
	for(int i=n;i>=1;i--){
		memset(vis,0,sizeof(vis));
		dfs(i,i);
		if(ans[i]==0){
			ans[i]=i;
			h++;
		}
		if(h==n)break;
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<" ";
	}
	return 0;
}
2025/1/22 14:54
加载中...