找城市

一张地图上有n个城市，城市和城市之间有且只有一条道路相连：要么直接相连，要么通过其它城市中转相连（可中转一次或多次）。城市与城市之间的道路都不会成环。

当切断通往某个城市 i 的所有道路后，地图上将分为多个连通的城市群，设该城市 i 的聚集度为 DPi（Degree of Polymerization）,  DPi = max(城市群1的城市个数， 城市群2的城市个数, ... 城市群m的城市个数)。

提示：如果有多个城市都满足条件，这些城市都要找出来（可能存在多个解）

提示：DPi 的计算，可以理解为已知一棵树，删除某个节点后，生成的多个子树，求解多个子树节点数的问题。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_set>

using namespace std;
int getDpi(const vector<unordered_set<int>> &vec,int index)
{
    //vec表示的是城市网，index表示当前要破坏第几个城市的对外通道
    //遍历每个城市群。
    int result = 0;
    vector<int> used(vec.size()+1,false);    //用于判断有多少城市群。
    for(int i=1;i<vec.size();i++)
    {
        if(i==index) continue;
        if(used[i]) continue; 

        queue<int> myque;
        myque.push(i);
        int size = 0;
        used[i] = true;
        while(myque.size())
        {
            int cur = myque.front();
            myque.pop();
            size++;
            auto iter = vec[cur].begin();
            while(iter != vec[cur].end()){
                if(*iter!= index && used[*iter]==false){
                    myque.push(*iter);
                    used[*iter]=true;
                }
                iter++;
            }
        }
        if(result<size) result =size;
    }
    return result;
}


int main()
{
    int num;
    cin>>num;
    //题目意思：切断某个i城市对外的所有通道之后，有多少互不相交的城市群，城市群的个数作为dpi;
    //求所有的dpi，求最大的dpi，dpi有多少输出多少。
    vector<int> dp(num+1,0);
    vector<int> result;
    //问题：用什么来表达城市群呢、vector<int> vec[i]表示城市i能去的城市。
    vector<unordered_set<int>> vec(num+1);
    //构建城市网。
    for(int i=1;i<=num-1;++i){
        int a,b;
        cin>>a>>b;
        vec[a].insert(b);
        vec[b].insert(a);
    }
    
    //对每个城市对外的路都进行破坏。
    int max = num;
    for(int i=1;i<=num;i++)
    {
        dp[i] = getDpi(vec,i);
        if(dp[i]==max){
            result.push_back(i); 
        }
        else if(dp[i]<max)
        {
            max = dp[i];
            result.clear();
            result.push_back(i);
        }
    }
    
    sort(result.begin(),result.end());
    for(int i=0;i<result.size();i++){
        cout<<result[i];
        if(i!= result.size()-1) cout<<' ';
    }
    return 0;
}

#include <bits/stdc++.h>

#define MAXN 1234

using namespace std;

vector<int> edge[MAXN];
int n, fr, to;
int res_min;
vector<int> res_node;
int vis[MAXN];
int cnt[MAXN];

void dfs(int u, int pos, int no) {
    vis[u] = pos;
    for (int i = 0; i < edge[u].size(); i++) {
        int v = edge[u][i];
        if (v == no || vis[v] != 0)
            continue;
        dfs(v, pos, no);
    }
    return;
}

void init() {
    for (int i = 0; i < MAXN; i++) {
        edge[i].clear();
    }
    res_min = MAXN;
    res_node.clear();
}

int main() {
    init();

    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        cin >> fr >> to;
        edge[fr].push_back(to);
        edge[to].push_back(fr);
    }

    // 切断点
    for (int nod = 1; nod <= n; nod++) {
        // 染色
        memset(vis, 0, sizeof(vis));
        memset(cnt, 0, sizeof(cnt));
        for (int i = 1; i <= n; i++) {
            if (i == nod || vis[i] != 0) continue;
            dfs(i, i, nod);
        }
        // 计算
        int tmp = 0;
        for (int i = 1; i <= n; i++) {
            cnt[vis[i]]++;
        }
        for (int i = 1; i <= n; i++) {
            if (cnt[i] > tmp) {
                tmp = cnt[i];
            }
        }
        // 结果
        if (tmp < res_min) {
            res_min = tmp;
            res_node.clear();
            res_node.push_back(nod);
        } else if (tmp == res_min) {
            res_node.push_back(nod);
        }
    }
    for (int i = 0; i < (int)res_node.size(); i ++) {
        if (i == 0) {
            cout << res_node[i];
        } else {
            cout << " " << res_node[i];
        }
    }
    cout << "\n";
    return 0;
}

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

    static int getParent(int now, int[] p) {
        while (p[now] != now) {
            now = p[now];
        }
        return now;
    }

    static void join(int x, int y, int[] p) {
        int px = getParent(x, p);
        int py = getParent(y, p);
        if (px != py) {
            p[px] = py;
        }
    }

    static int deg(Node[] nodes, int exclude, int n) {
        int[] parent = new int[n + 1];
        for (int i = 1; i < n + 1; ++i)
            parent[i] = i;
        for (int i = 0; i < n - 1; ++i) {
            if (nodes[i].x == exclude || nodes[i].y == exclude) {
                continue;
            } else {
                join(nodes[i].x, nodes[i].y, parent);
            }
        }
        int[] num = new int[n + 1];
        int ans = 0;
        for (int i = 1; i < n + 1; ++i) {
            int pi = getParent(i, parent);
            num[pi]++;
            ans = Math.max(ans, num[pi]);
        }
        return ans;
    }

    public static void main(String[] args) {
        final Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Node[] nodes = new Node[n - 1];
        for (int i = 0; i < n - 1; ++i) {
            nodes[i] = new Node();
            nodes[i].x = scanner.nextInt();
            nodes[i].y = scanner.nextInt();
        }
        Node[] res = new Node[n];
        int min = n + 10;
        for (int i = 1; i <= n; ++i) {
            res[i - 1] = new Node();
            final int deg = deg(nodes, i, n);
            res[i - 1].x = i;
            res[i - 1].y = deg;
            min = Math.min(min, deg);
        }
        Arrays.sort(res, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                int r = o1.y - o2.y;
                if (r == 0)
                    return o1.x - o2.x;
                return r;
            }
        });
        for (int i = 0; i < n - 1; ++i) {
            if (res[i].y == min) {
                if (i != 0)
                    System.out.print(" ");
                System.out.print(res[i].x);
            }
        }
    }
}

class Node {
    int x;
    int y;
}