_lucky__dog_ @ 2022-01-17 13:02:21
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n, m, top, ans;
int s;
int st[1010], d[1010], g[1010][1010], c[1010];
int q[1010];
int w[1010]; //表示每个车站的层数。
bool v[1010], mp[1010][1010];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i ++ )
{
memset(v, 0, sizeof v);
scanf("%d", &s);
for (int j = 1; j <= s; j ++ )
{
scanf("%d", &st[j]); v[st[j]] = 1;
}
for (int j = st[1]; j <= st[s]; j ++ )
{
if(v[j]) continue;
for (int k = 1; k <= s; k ++ )
{
if(mp[st[k]][j]) continue;
mp[st[k]][j] = 1; //连一条从 a[k] 到 j 的有向边,代表 a[k] 的级别大于 j。
d[j] ++; //更新一下 j 的入度。
g[st[k]][++ c[st[k]]] = j;
}
}
}
for (int i = 1; i <= n; i ++ )
{
if(d[i] == 0) q[++ top] = i, w[i] = 1;
}
while (top)
{
int t = q[top];
top --;
for (int i = 1; i <= c[t]; i ++ )
{
int v = g[t][i];
d[v] --;
w[v] = w[t] + 1;
ans = max(ans, w[v]);
if(d[v] == 0) q[++ top] = v;
}
}
printf("%d", ans);
return 0;
}
by bamboo12345 @ 2022-03-19 09:10:26
@努力的邱_Hella
w[v] = w[t] + 1;
这句不对,应改为
w[v] = max(w[v], w[t] + 1);
因为这个点我们要取最大指向它的
by _lucky__dog_ @ 2022-03-21 18:14:32
@bamboo123 谢谢,已经 AC 了