紧急疏散

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,x,y;
    cin>>n;
    vector<int> v[n+1];
    for(int i=0;i<n-1;i++){
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    vector<int> child;
    queue<int> q;
    bool vis[n+1];
    memset(vis,false,sizeof(vis));
    vis[1] = true;
    int r = 0;
    for(int i=0;i<v[1].size();i++){
        child.push_back(v[1][i]);
        vis[v[1][i]] = true;
    }
    for(int i=0;i<child.size();i++){
        q.push(child[i]);
        int cnt=0;
        while(!q.empty()){
            int p = q.front();
            cnt++;
            vis[p] = true;
            for(int j=0;j<v[p].size();j++)
                if(!vis[v[p][j]])
                    q.push(v[p][j]);
            q.pop();
        }
        r = max(r, cnt);
    }
    cout<<r<<endl;
    return 0;
}

package main

import(
    "bufio"
    "os"
    "strings"
    "strconv"
    "fmt"
)

func main(){
	input:=bufio.NewScanner(os.Stdin)
	input.Scan()
	n,_:=strconv.Atoi(input.Text())

	m:=make([][]int,n+1)
	visited:=make([]bool,n+1)

	for k:=0;k<n-1;k++{
		input.Scan()
		nums:=strings.Split(input.Text()," ")
		var temp [2]int
		for i,j:=range nums{
			num,_:=strconv.Atoi(j)
			temp[i]=num
		}
		m[temp[0]]=append(m[temp[0]],temp[1])
		m[temp[1]]=append(m[temp[1]],temp[0])
	}
	res:=0
	visited[1]=true
	for i:=0;i<len(m[1]);i++{
		visited[m[1][i]]=true
		que:=[]int{m[1][i]}
		temp:=0
		for len(que)!=0{
			temp++
			t:=que[0]
			que=que[1:]
			for j:=0;j<len(m[t]);j++{
				if !visited[m[t][j]]{
					que=append(que, m[t][j])
					visited[m[t][j]]=true
				}
			}
		}
		if temp>res{
			res=temp
		}
	}
	fmt.Println(res)
}

#include <iostream>
#include <vector>
#include <functional>

using namespace std;

int main(const int argc, const char* argv[]) {
  int n;
  cin >> n;
  vector<vector<int>> g(n + 1);
  for (int i = 0; i < n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }
  
  int ans = 0;
  function<int(int, int)> dfs = [&](int curr, int parent) -> int {
    int total = 0;
    for (const int nxt : g[curr]) {
      if (nxt == parent) continue;
      int numOfSubTree = dfs(nxt, curr);
      ans = max(ans, numOfSubTree);
      total += numOfSubTree;
    }
    return 1 + total;
  };
  
  dfs(1, 0);
  return printf("%d\n", ans), 0;
}

#include <vector>
#include <stdio.h>
   
using namespace std;
 // 使用并查集求出各个子树的最大节点数，即为最后结果
struct DSU {
    vector<int> f, cnt;
    // 初始化列表 f[i] 表示i的父节点的数值，起始值是其本身； cnt[i]表示 i节点下的所有子节点数 
    DSU(int n) : f(n), cnt(n, 1) {
        for (int i = 0; i < n; i++)
            f[i] = i;
    }
    int find(int x) {
        if (x == f[x]) return x;  // 简化了源代码，原是if (f[x] == f[f[x]]) return f[x]; 叶节点无子节点，返回叶节点的值
        return f[x] = find(f[x]);   // 无论新进来的节点父节点是谁，都遍历到其父节点的叶节点处接入新节点, 针对第一个例子：[2->3->4->5, 6]
    }                               // 这里f[x] = find(f[x]) 是进行了优化，使其直接映射到结尾，可以直接return find(f[x])，这样时间会变长
    bool merge(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx == fy) return false;
        f[fy] = fx;  //fy -> fx
        cnt[fx] += cnt[fy];
        return true;
    }
};
    
int main() {
    int n;
    scanf("%d", &n);
    DSU dsu(n+1);
    
    vector<int> root;
    for (int i = 1; i < n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        if (a == 1) root.push_back(b);
        else if (b == 1) root.push_back(a);
        else dsu.merge(a, b);
    }
    int ans = 0;
    for (int a : root) ans = max(ans, dsu.cnt[dsu.find(a)]); //找到叶节点对应的cnt值，取max
    printf("%d\n", ans);
    return 0;
}

对于大神算法的一点浅薄理解

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader df=new BufferedReader(new InputStreamReader(System.in));
        String sd;
        while((sd=df.readLine())!=null){
            int n=Integer.valueOf(sd);
            if(n<=1){
                System.out.println(0);
                return ;
            }
            HashMap<Integer,Set<Integer>> map=new HashMap<>();
            for(int i=1;i<=n;i++){
                Set<Integer> set=new HashSet<>();
                //set.add(i);
                map.put(i,set);
            }
            for(int i=0;i<n-1;i++){
                String[] gg=df.readLine().split(" ");
                int t1=Integer.valueOf(gg[0]);
                int t2=Integer.valueOf(gg[1]);
                map.get(t1).add(t2);
                map.get(t2).add(t1);
            }
            boolean[] res=new boolean[n+1];
            Deque<Integer> list=new LinkedList<>();
            res[1]=true;
            int max=0;
            for(Integer jj:map.get(1)){
                if(res[jj]){
                    continue;
                }
                list.add(jj);
                res[jj]=true;
                int num=0;
                while(!list.isEmpty()){
                 int size=list.size();
                for(int i=0;i<size;i++){
                    int k=list.poll();
                     num++;
                    for(Integer ff:map.get(k)){
                        if(res[ff]){
                            continue;
                        }
                            list.add(ff);
                            res[ff]=true;
                    }
                }
            }
              max=Math.max(max,num);
            }
            System.out.println(max);
        }
    }
}

#include <bits/stdc++.h>
using namespace std;

int dfs(vector<vector<int>>& adj, int i, int p) {
	int ans = 0;
	for (int son : adj[i]) {
		if (son == p) continue;
		ans += dfs(adj, son, i);
	}
	return 1 + ans;
}
int main() {
	int n;
	cin >> n;
	vector<vector<int>> adj(n + 1);
	int left, right;
	for (int i = 0; i < n - 1; i++) {
		cin >> left >> right;
		adj[left].push_back(right);
		adj[right].push_back(left);
	}
	int ans = 0;
	for (int son : adj[1]) {
		ans = max(ans, dfs(adj, son, 1));
	}
	cout << ans << endl;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
vector<int> v[100001];  //邻接表
bool vis[100001];       //访问标记

int dfs(int i){
	vis[i]=true;
	int sum=0;
	for(int j=0;j<v[i].size();j++){     //多叉树
		if(vis[v[i][j]]==false){
			sum+=dfs(v[i][j]);
		}
	}
	return sum+1;
}

int main(){
	int n,x,y;
	cin>>n;
	for(int i=0;i<n-1;i++){
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	for(int i=1;i<=n;i++)
	    vis[i]=false;
    vis[1]=true;
	int max=0;
	for(int i=0;i<v[1].size();i++){     //查找最多结点的子树
		x=dfs(v[1][i]);
		if(max<x)
		max=x;
	}
	cout<<max;
}

# 为啥只能过80%呢 
N = int(input())
graph = [set() for _ in range(N+1)]
for i in range(N-1):
    a, b= list(map(int, input().split()))
    graph[a].add(b)
    graph[b].add(a)

def dfs(index):
    if len(graph[index])==0:
        return 1
    count = 1
    while len(graph[index]) > 0:
        ind = graph[index].pop()
        graph[ind].remove(index)
        count += dfs(ind)
    return count
res = -1
while len(graph[1]) > 0:
    ind = graph[1].pop()
    graph[ind].remove(1)
    res = max(res, dfs(ind))
print(res)

# 为啥只能过 80% 呢

def find_deep(l, flag, x, deep):
    tmp = []
    for child in l[x]:
        if not flag[child]:
            flag[child] = True
            tmp.append(child)
    #
    if len(tmp) == 0:
        return deep
    if len(tmp) == 1:
        return find_deep(l, flag, tmp[0], deep+1)
    else:
        ans = 0
        for child in tmp:
            ans += find_deep(l, flag, child, 1)
        return ans + deep


if __name__ == "__main__":
    n = int(input())
    l = [[] for _ in range(n+1)]
    flag = [False for _ in range(n+1)]
    if n == 0 or n == 1:
        print(0)
    else:
        for i in range(n-1):
            x, y = map(int, input().strip().split(" "))
            l[x].append(y)
            l[y].append(x)
        ans = 0
        flag[1] = True
        tmp = []
        for child in l[1]:
            if not flag[child]:
                flag[child] = True
                tmp.append(child)
        for child in tmp:
            ans = max(ans, find_deep(l, flag, child, 1))
        print(ans)

解析来自：https://blog.csdn.net/qq_17550379/article/details/94459928

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

vector<list<int>> getTree(){
    int n;
    cin >> n;
    vector<list<int>> tree = vector<list<int>>(n, list<int>());
    while(--n){
        int l, r;
        cin >> l >> r;
        tree[l - 1].push_back(r - 1);
        tree[r - 1].push_back(l - 1);
    }
    return tree;
}

int bfs(vector<list<int>>& tree, int root, 
        vector<int>& queue, vector<char>& visited){
    /*
    // 为什么这两个数组生成放外面？ 申请内存是很费时间的一个操作，
    // 这两个数组可以复用，所以为了过最后10%才放外面
    int n = tree.size();
    vector<int> queue(n, 0);
    vector<char> visited(n, 0);
    */
    visited[0] = 1;      // 排除安全结点
    queue[0] = root;
    visited[root] = 1;
    int i = 0, j = 1;
    while(i < j){
        int cur = queue[i++];
        for(auto iter = tree[cur].begin(); iter != tree[cur].end();){
            if(!visited[*iter]) {
                queue[j++] = *iter;
                visited[*iter] = 1;
            }
            ++iter;
        }
    }
    return j;
}

int main(){
    auto tree = getTree();
    int retval = 0;
    if(!tree.empty()){
        int n = tree.size();
        vector<int> queue(n, 0);
        vector<char> visited(n, 0);
        for(auto iter = tree[0].begin(); iter != tree[0].end();){
            visited.assign(n, 0);
            retval = std::max(retval, bfs(tree, *iter, queue, visited));
            ++iter;
        }
    }
    cout << retval << '\n';
    return 0;
}