洛谷P1137旅行计划
思路：
题目说只能走到东边的城市，又保证
x
x
x再
y
y
y的西面，虽然说是双向道路，但是就可以直接建
(
x
,
y
)
(x,y)
(x,y)的边。 可以得到
d
p
[
v
]
=
max
(
d
p
[
v
]
,
d
p
[
u
]
+
1
)
dp[v]=\max(dp[v],dp[u]+1)
dp[v]=max(dp[v],dp[u]+1)，那么怎么解决后效性呢？就是用拓扑排序，因为拓扑排序出来的点就可以保证一个点不会再有入度，这样就不会受到别的点的影响，这样就没有了后效性。
代码：
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
#define cl(x,y) memset(x,y,sizeof(x))
#define ct cerr<<"Time elapsed:"<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define lson x<<1,l,mid
#define rson x<<1|1,mid+1,r
#define INF 1e18
const int N
=1e6+10;
const int mod
=1e9+7;
const int inf
=0x3f3f3f3f;
const double eps
=1e-8;
const double pi
=acos(-1);
using namespace std
;
struct edge
{
int u
,v
;
}e
[N
];
int head
[N
]={0},len
=0,in
[N
]={0},dp
[N
]={0};
void add(int u
,int v
)
{
e
[++len
]={head
[u
],v
};
head
[u
]=len
;
}
int main()
{
ios
::sync_with_stdio(false);
cin
.tie(0);cout
.tie(0);
int n
,m
,i
;
cin
>>n
>>m
;
for(i
=1;i
<=m
;i
++)
{
int u
,v
;
cin
>>u
>>v
;
add(u
,v
);
in
[v
]++;
}
queue
<int> q
;
for(i
=1;i
<=n
;i
++)
if(!in
[i
])
q
.push(i
);
while(!q
.empty())
{
int u
=q
.front();
q
.pop();
for(i
=head
[u
];i
;i
=e
[i
].u
)
{
int v
=e
[i
].v
;
dp
[v
]=max(dp
[u
]+1,dp
[v
]);
in
[v
]--;
if(!in
[v
])
q
.push(v
);
}
}
for(i
=1;i
<=n
;i
++)
cout
<<dp
[i
]+1<<endl
;
return 0;
}
