社区讨论
90分求助,#9TLE
P1983[NOIP 2013 普及组] 车站分级参与者 3已保存回复 8
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 8 条
- 当前快照
- 1 份
- 快照标识符
- @lodcjn4v
- 此快照首次捕获于
- 2023/10/31 04:22 2 年前
- 此快照最后确认于
- 2023/11/06 19:44 2 年前
CPP
#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_set>
#include <queue>
#include <iterator>
using namespace std;
unordered_set<int> G[1001];
int grade[1001], indegree[1001];
int n, m;
void build_graph()
{
cin >> n >> m;
while (m--)
{
int s;
cin >> s;
vector<int> a(s), b;
copy_n(istream_iterator<int>(cin), s, begin(a));
for (int i = a.front(), j = 0; i <= a.back(); i++)
{
if (i == a[j])
j++;
else
{
for (int v : a)
indegree[v] += G[i].insert(v).second;
}
}
}
}
int ans;
queue<int> Q;
void topsort()
{
for (int i = 1; i <= n; i++)
{
if (indegree[i] == 0)
{
Q.push(i);
grade[i] = 1;
}
}
while (!Q.empty())
{
int a = Q.front();
Q.pop();
for (auto b : G[a])
{
indegree[b]--;
grade[b] = max(grade[b], grade[a] + 1);
if (indegree[b] == 0)
Q.push(b);
}
ans = max(ans, grade[a]);
}
}
int main()
{
ios::sync_with_stdio(false);
build_graph();
topsort();
cout << ans;
return 0;
}
回复
共 8 条回复,欢迎继续交流。
正在加载回复...