有的题看似简单实则不易
【题目描述】
给出 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);
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;
}
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);
for(int i(1);i<=n;++i)
cout << d[scc[i]] << " ";
return 0;
}
|
(所以说有些题目还是没有想象中的那么简单啊…)