#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
vector<int> adj[N], adj_tmp[N];
int sum = 0;
int dfs(int i) {
int ret = 1;
for (auto &j : adj_tmp[i]) {
ret += dfs(j);
}
sum += ret;
return ret;
}
int main() {
int n; cin >> n;
for (int i = 1; i <= n; i++) {
int k; cin >> k;
for (int j = 1; j <= k; j++) {
int x; cin >> x;
adj[x].push_back(i);
}
}
int ans = INT_MAX;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
adj_tmp[j].clear();
}
queue<pair<int,int>> q; q.push({i, 0});
vector<int> vst(n + 1);
while (q.size()) {
auto i = q.front(); q.pop();
if (vst[i.first]) continue;
vst[i.first] = 1;
adj_tmp[i.second].push_back(i.first);
for (auto &j : adj[i.first]) {
q.push({j, i.first});
}
}
bool flag = false;
for (int j = 1; j <= n; j++) {
if (!vst[j]) {
flag = true;
break;
}
}
if (!flag) {
sum = 0;
dfs(i);
ans = min(ans, sum);
}
}
cout << ans << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
528 KB |
Output is correct |
5 |
Correct |
0 ms |
460 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
528 KB |
Output is correct |
5 |
Correct |
0 ms |
460 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
536 KB |
Output is correct |
8 |
Correct |
1 ms |
460 KB |
Output is correct |
9 |
Correct |
1 ms |
460 KB |
Output is correct |
10 |
Correct |
1 ms |
460 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
528 KB |
Output is correct |
5 |
Correct |
0 ms |
460 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
536 KB |
Output is correct |
8 |
Correct |
1 ms |
460 KB |
Output is correct |
9 |
Correct |
1 ms |
460 KB |
Output is correct |
10 |
Correct |
1 ms |
460 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
12 |
Correct |
30 ms |
732 KB |
Output is correct |
13 |
Correct |
22 ms |
744 KB |
Output is correct |
14 |
Correct |
267 ms |
744 KB |
Output is correct |
15 |
Correct |
34 ms |
732 KB |
Output is correct |
16 |
Correct |
969 ms |
876 KB |
Output is correct |
17 |
Correct |
1437 ms |
928 KB |
Output is correct |
18 |
Correct |
1384 ms |
1048 KB |
Output is correct |