首页 > > 程序设计 > C/C++ >

洛谷P3961 图的遍历

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

题目来源

做这道题的方法不少。

在这里我只提一种

就是大法师。

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