暴力做法
DFS(树的遍历)
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<stack>
#include<vector>
using namespace std;
const int N = 10010, M = 2 * N;
int n;
int e[M], ne[M], h[N], idx;
int dist[N], p[N];
stack<int> st[N];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u, int distance) {
dist[u] = distance;
for (int i = h[u]; i != -1; i = ne[i]) {
if (dist[e[i]] == -1) {
dfs(e[i], distance + 1);
}
}
}
int main() {
cin >> n;
memset(h, -1, sizeof h);
memset(p, -1, sizeof p);
memset(dist, -1, sizeof dist);
for (int i = 0; i < n; i++) {
int k;
cin >> k;
while (k--) {
int x;
cin >> x;
add(i, x);
p[x] = i;
}
}
int u;
for (int i = 0; i < n; i++)
if (p[i] == -1) u = i;
dfs(u, 1);
int res = 0;
for (int i = 0; i < n; i++) res = max(res, dist[i]);
cout << res << endl;
int num = 0;
for (int i = 0; i < n; i++) {
if (dist[i] == res) {
int t = i;
while (t != -1) {
st[num].push(t);
t = p[t];
}
num++;
}
}
vector<int> cnt;
while (!st[0].empty()) {
cnt.push_back(st[0].top());
st[0].pop();
}
for (int i = 1; i < num; i++) {
vector<int> temp;
while (!st[i].empty()) {
temp.push_back(st[i].top());
st[i].pop();
}
if (cnt > temp) {
cnt.clear();
cnt = temp;
}
}
cout << cnt[0];
for (int i = 1; i < cnt.size(); i++) cout << " " << cnt[i];
return 0;
}
树形DP
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 10010;
int n;
int e[N], ne[N], h[N], idx;
int son[N], p[N];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
//树形DP
int dfs(int u) {
int res = 0;//记录从当前节点的儿子结点出发的最长路径
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];//u的儿子节点编号
int d = dfs(j);//递归求从儿子结点j出发的最长路径
//接着进行判断,更新son数组
if (res < d) res = d, son[u] = j;
else if (res == d) son[u] = min(son[u], j);
}
return res + 1;
}
int main() {
cin >> n;
memset(son, -1, sizeof son);//将所有点的儿子都初始化为-1
memset(h, -1, sizeof h);
memset(p, -1, sizeof p);//将所有点的父亲都初始化为-1,用于找到根节点
for (int i = 0; i < n; i++) {
int k;
cin >> k;
while (k--) {
int x;
cin >> x;
add(i, x);
p[x] = i;
}
}
//找根节点
int root;
for (int i = 0; i < n; i++)
if (p[i] == -1) root = i;
cout << dfs(root) << endl;
while (root != -1) {
cout << root << " ";
root = son[root];
}
return 0;
}