反向图60分求调orz
查看原帖
反向图60分求调orz
371901
zbhujiaqi楼主2023/5/23 21:36
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<iomanip>
#include<list>
#include<queue>
#include<stack>
#include<deque>
using namespace std;
const int maxn = 100086;
struct node{
	int to,next;
}edge[maxn];//边集数组,对边数一般要设置比maxn*maxn大的数,题目有要求除外
int cnt;
int head[maxn];//头节点数组 
int ans[maxn];
void add(int u,int v)//添加一条边u-v 
{
	edge[cnt].to =v;
	edge[cnt].next =head[u];
	head[u]=cnt++;
}

void dfs(int u,int v)//u是倒序节点,v是搜索节点 
{
	if(ans[v])//对已经有值的节点不再遍历 
	    return;
	ans[v]=u;    
	for(int i=head[v];~i;i=edge[i].next )//i为边的序号 
	{
		int v1=edge[i].to ;
		dfs(u,v1);
	}
}

int main(){
//freopen("xxx.in",'r',stdin);
//freopen("xxx.out",'w',stdout);
    int n,m,x,y;
    cin>>n>>m;
    
	memset(head,-1,maxn);
    memset(ans,0,maxn);
    
	for(int i=0;i<m;i++)
    {
    	cin>>x>>y;
    	add(y,x);//添加反向边 
	}
     
    for(int i=n;i>0;i--){
        dfs(i,i);//倒序深度遍历	
	}
    for(int i=1;i<=n;i++){	
	    if(i!=1)
		    cout <<" ";
        cout<<ans[i];
    }
	return 0;
}
/*
4 3 
1 2
2 4
4 3
*/ 


2023/5/23 21:36
加载中...