首页 > 试题广场 >

紧急疏散

[编程题]紧急疏散
  • 热度指数:2230 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
体育场突然着火了,现场需要紧急疏散,但是过道真的是太窄了,同时只能容许一个人通过。现在知道了体育场的所有座位分布,座位分布图是一棵树,已知每个座位上都坐了一个人,安全出口在树的根部,也就是1号结点的位置上。其他节点上的人每秒都能向树根部前进一个结点,但是除了安全出口以外,没有任何一个结点可以同时容纳两个及以上的人,这就需要一种策略,来使得人群尽快疏散,问在采取最优策略的情况下,体育场最快可以在多长时间内疏散完成。

数据范围:

输入描述:
第一行包含一个正整数n,即树的结点数量。 接下来有n-1行,每行有两个正整数x,y,表示在x和y结点之间存在一条边。(1<=x,y<=n)


输出描述:
输出仅包含一个正整数,表示所需要的最短时间
示例1

输入

6
2 1
3 2
4 3
5 2
6 1

输出

4
C++抄的前面答案+offer+邻接表
/*
 这道题是找根节点下的最大子树
 因为是多叉树,可以利用图中的邻接表,这里利用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;
}


发表于 2019-08-05 22:12:37 回复(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;
}

发表于 2019-11-01 09:01:38 回复(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;
 
}


编辑于 2019-12-26 19:26:41 回复(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)
}

发表于 2022-04-04 11:37:46 回复(0)
#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;
}

发表于 2021-07-11 19:46:00 回复(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;
}

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

发表于 2023-11-27 02:27:06 回复(0)
这测试用例专门用来恶心python的吧,我是真服了。。。
思路就是找1的子节点为根的子树中,含有节点数的最大值
然后如果用dfs递归来找每个子树含有节点数量 ,只能过80%,报错 RecursionError: maximum recursion depth exceeded in comparison
老老实实用bfs或者dfs写迭代吧,正常来说用一个数组visited = [False]*(n+1)记录已经访问过的节点,这么写也只能通过80%,会提示超时
但是把visited设成一格集合,每次检查节点是否在集合中,这样子就能通过了。。。
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)
发表于 2022-02-15 19:29:02 回复(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);
        }
    }
}


发表于 2020-08-19 20:44:55 回复(0)
#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;
}

发表于 2020-08-06 10:59:45 回复(0)
一开始没看清题目,以为出口只能容纳俩人呢。其实就是求出根节点的各个子树的节点个数的最大值就是最终答案,节点遍历的基础问题,可以采用bfs
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);
    }
}


发表于 2020-05-12 16:16:34 回复(0)
BFS
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)
    


发表于 2020-04-22 22:25:39 回复(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;
}

发表于 2020-04-09 19:29:51 回复(0)
搞个并查集,给并查集附带一个isolate方法,意义是在union过程中如果发现union的节点双方有一个是1的话就不继续union,并将另一个节点和头结点原地互换(在这里用哈希表直接换索引内容),继而会得到k个并查集,其中一个只有1本身,另外k-1个分别是直接与1相连的节点为头部的子集们,返回size最大的即为最大需要时间。
感觉这个方法空间上不是很优,希望有大佬看到的话给点建议好啦
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);

    }

}


发表于 2020-03-17 18:10:23 回复(0)
就是求根节点所有的儿子所在树的最多节点个数。链式前向星+dfs
#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;
}


发表于 2020-03-11 15:24:35 回复(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)

发表于 2019-08-23 11:40:32 回复(1)
# 为啥只能过 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)

发表于 2019-08-05 23:41:33 回复(0)

解析来自: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;
}
发表于 2019-07-26 21:53:51 回复(0)