思路
好久没有写拓扑排序了。今天看到这题看了半天,由题解可知是拓扑序DP。原理根据拓扑序来进行DP。由于每个点在DAG是不会回路的,所以我们只需一头往下走就好,用dp[x]记录点x可到达的地方。使用拓扑排序就会让DP时不会出现影响其他已计算过的节点。
代码
// P1137.cpp
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 100010;
int points[maxn];
int to[2 * maxn];
int next[2 * maxn];
int indeg[maxn];
int res[maxn];
int dp[maxn];
int tot = 0;
int current = 0;
int n, m;
void add_edge(int a, int b)
{
to[current] = b;
next[current] = points[a];
points[a] = current++;
}
void toposort()
{
queue<int> waiting;
for (int i = 1; i <= n; i++)
if (indeg[i] == 0)
waiting.push(i), res[tot++] = i;
while (!waiting.empty())
{
int curt = waiting.front();
waiting.pop();
for (int edge = points[curt]; edge != -1; edge = next[edge])
{
indeg[to[edge]]--;
if (indeg[to[edge]] == 0)
waiting.push(to[edge]), res[tot++] = to[edge];
}
}
}
void DP()
{
for (int i = 1; i <= n; i++)
dp[i] = 1;
for (int i = 0; i < n; i++)
for (int edge = points[res[i]]; edge != -1; edge = next[edge])
dp[to[edge]] = max(dp[to[edge]], dp[res[i]] + 1);
}
int main()
{
memset(points, -1, sizeof(points));
memset(to, -1, sizeof(to));
memset(indeg, 0, sizeof(indeg));
cin >> n >> m;
int a, b;
for (int i = 0; i < m; i++)
{
cin >> a >> b, add_edge(a, b);
indeg[b] += 1;
}
toposort();
DP();
for (int i = 1; i <= n; i++)
cout << dp[i] << endl;
return 0;
}
// P1137.cpp
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 100010;
int points[maxn];
int to[2 * maxn];
int next[2 * maxn];
int indeg[maxn];
int res[maxn];
int dp[maxn];
int tot = 0;
int current = 0;
int n, m;
void add_edge(int a, int b)
{
to[current] = b;
next[current] = points[a];
points[a] = current++;
}
void toposort()
{
queue<int> waiting;
for (int i = 1; i <= n; i++)
if (indeg[i] == 0)
waiting.push(i), res[tot++] = i;
while (!waiting.empty())
{
int curt = waiting.front();
waiting.pop();
for (int edge = points[curt]; edge != -1; edge = next[edge])
{
indeg[to[edge]]--;
if (indeg[to[edge]] == 0)
waiting.push(to[edge]), res[tot++] = to[edge];
}
}
}
void DP()
{
for (int i = 1; i <= n; i++)
dp[i] = 1;
for (int i = 0; i < n; i++)
for (int edge = points[res[i]]; edge != -1; edge = next[edge])
dp[to[edge]] = max(dp[to[edge]], dp[res[i]] + 1);
}
int main()
{
memset(points, -1, sizeof(points));
memset(to, -1, sizeof(to));
memset(indeg, 0, sizeof(indeg));
cin >> n >> m;
int a, b;
for (int i = 0; i < m; i++)
{
cin >> a >> b, add_edge(a, b);
indeg[b] += 1;
}
toposort();
DP();
for (int i = 1; i <= n; i++)
cout << dp[i] << endl;
return 0;
}
// P1137.cpp #include <iostream> #include <cstring> #include <queue> using namespace std; const int maxn = 100010; int points[maxn]; int to[2 * maxn]; int next[2 * maxn]; int indeg[maxn]; int res[maxn]; int dp[maxn]; int tot = 0; int current = 0; int n, m; void add_edge(int a, int b) { to[current] = b; next[current] = points[a]; points[a] = current++; } void toposort() { queue<int> waiting; for (int i = 1; i <= n; i++) if (indeg[i] == 0) waiting.push(i), res[tot++] = i; while (!waiting.empty()) { int curt = waiting.front(); waiting.pop(); for (int edge = points[curt]; edge != -1; edge = next[edge]) { indeg[to[edge]]--; if (indeg[to[edge]] == 0) waiting.push(to[edge]), res[tot++] = to[edge]; } } } void DP() { for (int i = 1; i <= n; i++) dp[i] = 1; for (int i = 0; i < n; i++) for (int edge = points[res[i]]; edge != -1; edge = next[edge]) dp[to[edge]] = max(dp[to[edge]], dp[res[i]] + 1); } int main() { memset(points, -1, sizeof(points)); memset(to, -1, sizeof(to)); memset(indeg, 0, sizeof(indeg)); cin >> n >> m; int a, b; for (int i = 0; i < m; i++) { cin >> a >> b, add_edge(a, b); indeg[b] += 1; } toposort(); DP(); for (int i = 1; i <= n; i++) cout << dp[i] << endl; return 0; }
%%%,太优秀了