欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

洛谷P3961 图的遍历

程序员文章站 2022-08-15 08:44:25
题目来源 做这道题的方法不少。 在这里我只提一种 就是大法师。 可以采用反向建边,从最大的点开始dfs 我们考虑每次从所剩点中最大的一个点出发,我们暂且称它为i,而凡是i这个点所能到达的点,可以到达的点最大都是i。 在遍历的时候按n——>1的顺序 因为是从大到小遍历,故每个点第一次被碰到的i一定是这 ......

 

做这道题的方法不少。

在这里我只提一种

就是大法师。

可以采用反向建边,从最大的点开始dfs

我们考虑每次从所剩点中最大的一个点出发,我们暂且称它为i,而凡是i这个点所能到达的点,可以到达的点最大都是i。

在遍历的时候按n——>1的顺序

因为是从大到小遍历,故每个点第一次被碰到的i一定是这个点最大可到达的点

代码如下

#include<iostream>
#define maxx 500010
using namespace std;
int n,m;

struct pp {
    int next,to;
} edge[maxx];
int cnt;
int head[maxx];

int a[maxx];//存储答案
void add(int u,int v) {        //邻接表
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}
void dfs(int x,int k) {
    if(a[x]) return ;    //处理环,同时保存最优解
    a[x]=k;
    for(int i=head[x]; i; i=edge[i].next)//遍历可以到达的点
        dfs(edge[i].to,k);
}
inline void init() {        
    for(int i=1; i<=n; i++)
        head[i]=-1;
}
int main() {
    cin>>n>>m;
    init();        //初始化
    for(int i=1; i<=m; i++) {
        int u,v;
        cin>>u>>v;
        add(v,u);    //反向建边
    }
    for(int i=n; i>=1; i--) dfs(i,i);    递归搜索
    for(int i=1; i<=n; i++) cout<<a[i]<<' ';
}

同时可以使用vector,代码更为易读,变量同上

#include<iostream>
#include<vector>
#define maxx 500100
using namespace std;
int n,m;
vector<int > edge[maxx];
int a[maxx];
void dfs(int x,int k) {
    if(a[x]) return ;
    a[x]=k;
    for(int i=0; i<edge[x].size(); i++)
        dfs(edge[x][i],k);
}
int main() {
    cin>>n>>m;
    for(int i=1; i<=m; i++) {
        int u,v;
        cin>>u>>v;
        edge[v].push_back(u);
    }
    for(int i=n; i>=1; i--) dfs(i,i);
    for(int i=1; i<=n; i++) cout<<a[i]<<' ';
}