(luogu3916)图的遍历

发表于 | 分类于 ，

有的题看似简单实则不易

【题目描述】

给出n个点, m条边的有向图, 对于每个点v, 求从v出发能到达的编号最大的点

【输入输出】

输入格式：

第一行为两个整数n,m

接下来m行, 每行2个整数u,v, 表示u到v有条有向边, 点用1到n的数字编号

输出格式:

n个整数, 表示从i能到达的最大编号的结点

思路:

一开始想用dp解决, 但WA了6个点

后来发现这张图不一定是DAG, 无法直接使用dp

于是就只能先用tarjan把图缩成DAG, 再用dp解决

(貌似题解中说可以反向bfs, 没试过所以没有代码)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;
const int Mn(100005);
const int Mm(100005);
int n,m;
struct edge
{
    int e;
    edge *next;
}*v[Mn],E[Mm]; //边表
edge *vd[Mn],Ed[Mm];
int t(0),scn(0);
int pre[Mn],low[Mn],scc[Mn],f[Mn];
stack<int> S;
int tar(int x)
{
    pre[x] = ++t;
    low[x] = t;
    S.push(x);
    for(edge* e(v[x]);e;e=e->next)
    {
        if(!pre[e->e])
        {
            tar(e->e);
            low[x] = min(low[x],low[e->e]);
        }
        else if(!scc[e->e])
            low[x] = min(low[x],pre[e->e]);
    }
    if(pre[x]==low[x])
    {
        ++scn;
        while(true)
        {
            int u(S.top()); S.pop();
            scc[u] = scn;
            f[scn] = max(f[scn],u);
            if(x==u)	break;
        }
    }
}
int sin[Mn];
int topo[Mn],d[Mn];
int mdfs(int i) //记忆化搜索
{
    if(d[i])    return d[i];
    d[i] = f[i];
    for(edge* e(vd[i]);e;e=e->next)
        d[i] = max(d[i],mdfs(e->e));
    return d[i];
}
int main()
{
    cin >> n >> m;
    for(int i(1);i<=m;++i)
    {
        int s,e;
        scanf("%d %d",&s,&e); //读入图
        E[i].e = e, E[i].next = v[s];
        v[s] = E+i;
    }
    for(int i(1);i<=n;++i)
        if(!pre[i])	tar(i); //tarjan找scc
    /*----缩点----*/
    int ecn(0);
    for(int i(1);i<=n;++i)
        for(edge* e(v[i]);e;e=e->next)
            if(scc[i]!=scc[e->e])
            {
                ++sin[scc[e->e]];
                Ed[++ecn].e=scc[e->e], Ed[ecn].next=vd[scc[i]];
                vd[scc[i]] = Ed+ecn;
            }
    /*--------*/
    /*----拓扑排序并dp----*/
    int h(1),t(1);
    for(int i(1);i<=scn;++i)
        if(!sin[i])	topo[t++] = i;
    while(h!=t)
    {
        for(edge* e(vd[topo[h]]);e;e=e->next)
        {
            --sin[e->e];
            if(!sin[e->e])	topo[t++] = e->e;
        }
        ++h;
    }
    for(int i(t-1);i>0;--i)
        mdfs(i); //按照拓扑逆序dp
    for(int i(1);i<=n;++i)
        cout << d[scc[i]] << " ";
    return 0;
}

(所以说有些题目还是没有想象中的那么简单啊…)