#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
vector<vector<int>> q(50001);
int sum[50001];
int vis[50001];
void dfs(int i,int t, int s) {
sum[i] += s;
vis[t] = 1;
for (vector<int>::iterator j = q[t].begin(); j < q[t].end(); j++) {
if (!vis[*j]) {
dfs(i,*j,s+1);
}
}
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int a, b;
cin >> a, b;
q[a].push_back(b);
q[b].push_back(a);
}
for (int i = 1; i <= n; i++) {
dfs(i, i, 0);
memset(vis, 0, sizeof(vis));
}
int min = 65535, k = 0;
for (int i = 1; i <= n; i++) {
if (sum[i] < min) {
min = sum[i];
k = i;
}
}
cout << k << ' ' << min;
这是代码
#include <vector>
#include <string.h>
using namespace std;
vector<vector<int>> q(50001);
int sum[50001];
int vis[50001];
void dfs(int i,int t, int s) {
sum[i] += s;
vis[t] = 1;
for (vector<int>::iterator j = q[t].begin(); j < q[t].end(); j++) {
if (!vis[*j]) {
dfs(i,*j,s+1);
}
}
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int a, b;
cin >> a, b;
q[a].push_back(b);
q[b].push_back(a);
}
for (int i = 1; i <= n; i++) {
dfs(i, i, 0);
memset(vis, 0, sizeof(vis));
}
int min = 65535, k = 0;
for (int i = 1; i <= n; i++) {
if (sum[i] < min) {
min = sum[i];
k = i;
}
}
cout << k << ' ' << min;
这是代码