C++14(g++5.4) 解法, 执行用时: 28ms, 内存消耗: 3556K, 提交时间: 2020-07-02 10:07:17

#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;

vector<int> v[50005];
int n,m,a,b,minn=(1<<30),f[50005],s[50005];

void dfs(int x,int fa){
  s[x]=1;
  for(int i=0;i<v[x].size();i++){
    int u=v[x][i];
    if(u==fa)continue;
    dfs(u,x);
    s[x]+=s[u];
    f[x]=max(f[x],s[u]);
  }
  f[x]=max(f[x],n-s[x]);
  return;
}

int main(){
  scanf("%d%d",&n,&m);
  for(int i=1;i<=m;i++){
    scanf("%d%d",&a,&b);
    v[a].push_back(b);
    v[b].push_back(a);
  }
  dfs(1,0);
  for(int i=1;i<=n;i++)minn=min(minn,f[i]);
  for(int i=1;i<=n;i++)if(f[i]==minn)printf("%d ",i);
  return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 24ms, 内存消耗: 3448K, 提交时间: 2020-03-15 11:40:53

#include<bits/stdc++.h>
using namespace std;
vector<int>ve[50005];
int f[50005],s[50005],n,mi=999999;
void dfs(int x,int fa)
{
	s[x]=1;
	for(int i=0;i<ve[x].size();i++)
	{
		int v=ve[x][i];
		if(v==fa) continue;
		dfs(v,x);
		s[x]+=s[v];
		f[x]=max(f[x],s[v]);
	}
	f[x]=max(f[x],n-s[x]);
	return;
}
int main()
{
	int m,a,b;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&a,&b);
		ve[a].push_back(b);
		ve[b].push_back(a);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++)
	mi=min(mi,f[i]);
	for(int i=1;i<=n;i++)
	if(f[i]==mi) printf("%d ",i);
	printf("\n");
	return 0;
}