洛谷P3961 图的遍历

2019-05-24 06:10:02来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

题目来源

 

做这道题的方法不少。

在这里我只提一种

就是大法师。

可以采用反向建边,从最大的点开始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]<<' ';
}

 


原文链接:https://www.cnblogs.com/skkyk/p/10914819.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:C++中组合和继承的概念及意义

下一篇:C++中的三种继承方式