#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
constexpr int maxN = 500000;
vector<int> adj[maxN + 1];
int tree[maxN + 1];
int id = 0;
void dfs(int a) {
for (int b : adj[a]) {
dfs(b);
tree[a] += tree[b];
}
if (tree[a] == 0) tree[a]++;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
int total = 0;
vector<vector<int>> arr(n);
{
int k; cin >> k;
total += k;
arr[0].assign(k, 0);
for (int i = 0; i < k; i++) {
arr[0][i] = ++id;
}
}
for (int i = 1; i < n; i++) {
int k; cin >> k;
total += k;
arr[i].assign(k, 0);
for (int j = 0; j < k; j++) {
int a; cin >> a;
arr[i][j] = ++id;
if (a == 0) continue;
adj[arr[i - 1][a - 1]].push_back(id);
}
}
int maxi = 0;
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = 0; j < (int)arr[i].size(); j++) {
if (tree[arr[i][j]] == 0) {
dfs(arr[i][j]);
}
sum += tree[arr[i][j]];
// cerr << tree[arr[i][j]] << ' ';
}
maxi = max(maxi, sum);
// cerr << '\n';
}
cout << maxi << '\n';
return 0;
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | #include <bits/stdc++.h> #define endl '\n' using namespace std; constexpr int maxN = 500000; vector<int> adj[maxN + 1]; int tree[maxN + 1]; int id = 0; void dfs(int a) { for (int b : adj[a]) { dfs(b); tree[a] += tree[b]; } if (tree[a] == 0) tree[a]++; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; int total = 0; vector<vector<int>> arr(n); { int k; cin >> k; total += k; arr[0].assign(k, 0); for (int i = 0; i < k; i++) { arr[0][i] = ++id; } } for (int i = 1; i < n; i++) { int k; cin >> k; total += k; arr[i].assign(k, 0); for (int j = 0; j < k; j++) { int a; cin >> a; arr[i][j] = ++id; if (a == 0) continue; adj[arr[i - 1][a - 1]].push_back(id); } } int maxi = 0; for (int i = 0; i < n; i++) { int sum = 0; for (int j = 0; j < (int)arr[i].size(); j++) { if (tree[arr[i][j]] == 0) { dfs(arr[i][j]); } sum += tree[arr[i][j]]; // cerr << tree[arr[i][j]] << ' '; } maxi = max(maxi, sum); // cerr << '\n'; } cout << maxi << '\n'; return 0; } |
English