P3916 图的遍历 dfs

题目描述

给出

输入输出格式

输入格式：

第1 行，2 个整数

接下来 $MM行，每行2个整数U_i,V_iUi,Vi，表示边(U_i,V_i)(Ui,Vi)。点用1, 2,cdots,N1,2,⋯,N编号。$

输出格式：

N 个整数

$一开始疯狂想着dfs 但是有环很难处理$

$有环可以用tarjan来解$

$还有一种巧妙的方法：$

$如果将题目改成染成颜色最小的那么就很好解了带着最小的颜色遍历一遍即可$

$所以我们可以反向建边然后倒着dfs一遍就行了QAQ$

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define REP(i,N)  for(int i=0;i<(N);i++)
#define CLR(A,v)  memset(A,v,sizeof A)
//////////////////////////////////
#define inf 0x3f3f3f3f
const int N=1e5+5;
vector<int>edge[N];
int n,m,ans[N],vis[N];

void dfs(int u,int flag)
{
    if(ans[u])return ;
    ans[u]=flag;
    for(int i=0;i<edge[u].size();i++)
    dfs(edge[u][i],flag);
}
int main()
{
    RII(n,m);
    rep(i,1,m)
    {
        int a,b;RII(a,b);edge[b].push_back(a);
    }
    repp(i,n,1)
    if(!ans[i])
    dfs(i,i);

    rep(i,1,n)
    printf("%d ",ans[i]);

    return 0;
}

View Code

两种dfs都值得学习：

int dfs(int u)
{
    if(f[u])return f[u];
    f[u]=MAX[u];
    for(int i=head[u];i;i=e[i].next)
    {
        f[u]=max(f[u],dfs(e[i].to));
    }
    return f[u];
}

void dfs(int x)                     //记忆化搜索
{
    if(f[x]) return;
    f[x] = MAX[x];                  //当前强联通分量中的最大值
    for(int i=head[x];i;i=e[i].next)
    {
        int to = e[i].to;
        if(!f[to]) dfs(to);
        f[x] = max(f[x],f[to]);     // 子树中的最大值
    }
}

View Code