体育场突然着火了,现场需要紧急疏散,但是过道真的是太窄了,同时只能容许一个人通过。现在知道了体育场的所有座位分布,座位分布图是一棵树,已知每个座位上都坐了一个人,安全出口在树的根部,也就是1号结点的位置上。其他节点上的人每秒都能向树根部前进一个结点,但是除了安全出口以外,没有任何一个结点可以同时容纳两个及以上的人,这就需要一种策略,来使得人群尽快疏散,问在采取最优策略的情况下,体育场最快可以在多长时间内疏散完成。
数据范围: ![](https://www.nowcoder.com/equation?tex=1%20%5Cle%20n%20%5Cle%2010%5E5%20%5C)
第一行包含一个正整数n,即树的结点数量。 接下来有n-1行,每行有两个正整数x,y,表示在x和y结点之间存在一条边。(1<=x,y<=n)
输出仅包含一个正整数,表示所需要的最短时间
6 2 1 3 2 4 3 5 2 6 1
4
/* 这道题是找根节点下的最大子树 因为是多叉树,可以利用图中的邻接表,这里利用vector和list实现 先记录根节点下的次子节点子节点。分别以次子节点为根,然后利用广度优先或者深度优先遍历计算得到各个节点的子树节点总和 取次子节点中最大的值作为结果 */ #include<bits/stdc++.h> using namespace std; int main() { int m;cin >> m; vector<list<int>> vec(m, list<int>()); int x,y; //创建邻接表 while(cin >>x >>y) { vec[x-1].push_back(y-1); vec[y-1].push_back(x-1); } queue<int> que; map<int, int> mac; vector<bool> vis(m, false); vector<int> subNode; vis[0] = true; int res = 0; //得到次子节点 for(auto it = vec[0].begin();it!=vec[0].end();it++) { subNode.push_back(*it); vis[*it] = true; } //遍历次子节点分别求子树节点个数 for(int i = 0; i < subNode.size();i++) { que.push(subNode[i]); int num = 0; while(!que.empty()) { int tem = que.front(); num++; vis[tem] = true; for(auto it = vec[tem].begin(); it != vec[tem].end(); it++) { if(!vis[*it]) { que.push(*it); } } que.pop(); } res = res < num ? num : res; } cout << res << endl; return 0; }
#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; }
#include <vector> #include <stdio.h> using namespace std; // 使用并查集求出各个子树的最大节点数,即为最后结果 struct DSU { vector<int> f, cnt; DSU(int n) : f(n), cnt(n, 1) { for (int i = 0; i < n; i++) f[i] = i; } int find(int x) { if (f[x] == f[f[x]]) return f[x]; return f[x] = find(f[x]); } bool merge(int x, int y) { int fx = find(x), fy = find(y); if (fx == fy) return false; f[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)]); printf("%d\n", ans); 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; } 对于大神算法的一点浅薄理解
from collections import defaultdict n = int(input()) d = defaultdict(set) for _ in range(n-1): a, b = map(int, input().split()) d[a].add(b) d[b].add(a) ''' def dfs(x, pre): # 写成递归会报错,只能过80% global res # dfs返回x及以下总结点数 total = 0 # total记录所有子节点的总节点数之和 for nxt in d[x]: # 对所有子节点递归 if nxt != pre: tmp = dfs(nxt, x) total += tmp if tmp > res: res = tmp # 题目最后答案为节点1所有子节点中总节点数的最大值 return 1 + total res = 0 dfs(1,-1) print(res) ''' res = 0 # 迭代法,输出res为1的所有子节点的树所含节点最大值 for nxt in d[1]: visited = set([1,nxt]) # 这里visited如果设置成数组[False]*(n+1),就会超时 q = [nxt] # dfs cnt = 0 # cnt记录每个子节点的树中节点总量 while q: cur = q.pop() cnt += 1 for i in d[cur]: if i not in visited: q.append(i) visited.add(i) if cnt > res: res = cnt print(res)
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; }
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.HashMap; import java.util.LinkedList; import java.util.Queue; /** * @Author: coderjjp * @Date: 2020-05-12 8:46 * @Description: 紧急疏散 * @version: 1.0 */ public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>(); for (int i = 0; i < n - 1; i++){ String line[] = br.readLine().split(" "); int f = Integer.parseInt(line[0]); int t = Integer.parseInt(line[1]); if (!graph.containsKey(f)) graph.put(f, new ArrayList<>()); if (!graph.containsKey(t)) graph.put(t, new ArrayList<>()); graph.get(f).add(t); graph.get(t).add(f); } Queue<Integer> queue = new LinkedList<>(); boolean flag[] = new boolean[n+1]; ArrayList<Integer> subNode = new ArrayList<>(); flag[1] = true; int res = 0; //得到次子节点 if (graph.containsKey(1)) for(Integer it: graph.get(1)){ subNode.add(it); flag[it] = true; } //遍历次子节点分别求子树节点个数 for(int i = 0; i < subNode.size();i++){ queue.offer(subNode.get(i)); int num = 0; while(!queue.isEmpty()){ int tem = queue.poll(); num++; flag[tem] = true; if (graph.get(tem) != null) for (int nextNode: graph.get(tem)){ if (!flag[nextNode]){ queue.offer(nextNode); flag[nextNode] = true; } } } res = Math.max(res, num); } System.out.println(res); } }
from collections import defaultdict tree = defaultdict(list) n = int(input()) for _ in range(n-1): x,y = map(int,input().split()) tree[x].append(y) tree[y].append(x) def bfs(node,tree): c = 1 queue = [node] visited = set() visited.add(1) visited.add(node) while queue: tmp = queue.pop(0) for d in tree[tmp]: if d not in visited: c+=1 queue.append(d) visited.add(d) return c max_value = 0 for node in tree[1]: max_value = max(bfs(node,tree),max_value) print(max_value)
#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; }
import java.util.HashMap; import java.util.Scanner; public class Main { public static class ufsNode{ int id; public ufsNode(int id){this.id = id;} } public static class UFS{ HashMap<ufsNode,ufsNode> father; HashMap<ufsNode,Integer> size; HashMap<Integer,ufsNode> index; public UFS(int nodeNum){ father = new HashMap<>(); size = new HashMap<>(); index = new HashMap<>(); for (int i = 1; i < nodeNum+1; i++) { ufsNode node = new ufsNode(i); index.put(i,node); father.put(node,node); size.put(node,1); } } public ufsNode find(ufsNode n){ ufsNode f = father.get(n); if(n!=f) return find(f); father.put(n,f); return f; } public void isolate(ufsNode node){ ufsNode head = find(node); if(node!=head){ int curNum = node.id; int headNum = head.id; head.id = curNum; node.id = headNum; index.put(curNum,head); index.put(headNum,node); } } public void union(int a,int b){ ufsNode nodeA = index.get(a); ufsNode nodeB = index.get(b); if(a==1) { isolate(nodeB); return; } if(b==1) { isolate(nodeA); return; } ufsNode aHead = find(nodeA); ufsNode bHead = find(nodeB); if(aHead==bHead) return; if(size.get(aHead)<=size.get(bHead)){ father.put(aHead,bHead); size.put(bHead,size.get(aHead)+size.get(bHead)); }else{ father.put(bHead,aHead); size.put(aHead,size.get(aHead)+size.get(bHead)); } } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int size=0; if(sc.hasNextInt()) size = sc.nextInt(); UFS ufs = new UFS(size); while(sc.hasNextInt()){ ufs.union(sc.nextInt(),sc.nextInt()); } int res = 0; for (int i = 2; i < size+1; i++) { res = Math.max(res,ufs.size.get(ufs.index.get(i))); } System.out.println(res); } }
#include<bits/stdc++.h> using namespace std; const int N=100005; int cnt,head[N],n; struct edge{ int v,next; }e[N<<1]; void add(int u,int v) { e[++cnt].v=v; e[cnt].next=head[u]; head[u]=cnt; } int dfs(int f,int u) { int tmp=1; for(int i=head[u];i;i=e[i].next) { int v=e[i].v; if (v!=f) { tmp+=dfs(u,v); } } return tmp; } int main() { cin>>n; int u,v,ans=0; for(int i=1;i<=n-1;i++) { cin>>u>>v; add(u,v); add(v,u); } for(int i=head[1];i;i=e[i].next) { int v=e[i].v; ans=max(ans,dfs(1,v)); } cout<<ans; return 0; }
# 为啥只能过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; }