保研机试训练Day-11

图的存储

树的深度优先遍历

给定一颗树，树中包含 n 个结点（编号 1∼n）和 n−1 条无向边。

请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

详细分析：树的深度优先遍历dfs(u)最大的好处: 在遍历过程中可以算出以u为根节点的树中结点的数量. 本题的本质是树的dfs，每次dfs可以确定以u为重心的最大连通块的节点数，并且更新一下ans。也就是说，dfs并不直接返回答案，而是在每次更新中迭代一次答案。

各个变量意义: sum表示以这一点为根结点的树中所有结点个数 res表示删除这一点后的连通块中结点数目的最大值(不断更新) ans表示所有(依次删除每个结点的情况)最大连通结点数目的最小值,即各个res的最小值(不断更新) 所有备注可结合上方图示一起看

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1e5+10, M=N*2;

int h[N],e[M],ne[M],idx;
bool st[N];
int n,m;
int ans = N;

void add(int a,int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

//以u为根的子树中点的数量
int dfs(int u){
    st[u] = true; //标记当前点已经被搜过了
  
    int sum = 1,res = 0; //sum是当前子树的大小 res是子数组的大小
    for(int i = h[u];i != -1;i = ne[i]){
        int j = e[i];
        if(!st[j]){
            int s = dfs(j);
            res = max(res, s);
            sum += s;
        } 
    }
  
    res = max(res, n - sum);
    ans = min(ans, res);
    return sum;
}
int main(){
    cin >> n;
    memset(h,-1,sizeof h);
    for(int i = 0; i < n - 1; i++){
        int a,b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    dfs(1);
    cout << ans << endl;
    return 0;
}

树与图的广度优先遍历

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环。

所有边的长度都是 1，点的编号为 1∼n。

请你求出 1 号点到 n 号点的最短距离，如果从 1 号点无法走到 n 号点，输出 −1。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5+10;

int n,m;
int h[N],e[N],ne[N],idx; // 邻接表数据结构
int d[N];                // 保存1号点到各个点的距离
int q[N];

void add(int a,int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
int bfs(){
    int hh=0,tt=0;
    q[0] = 1;
    memset(d, -1, sizeof d);
    d[1] = 0;
    while(hh<=tt){
        int t = q[hh++];
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(d[j]==-1){
                d[j] = d[t] + 1;
                q[++tt] = j;
            }
        }
    }
    return d[n];
}
int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    cout << bfs() << endl;
    return 0;
}

拓扑排序

给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。

若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。

#include<bits/stdc++.h>
using namespace std;
int n,m;                 //保存图的点数和边数
const int N = 1e5+10;
int h[N],e[N],ne[N],idx; //队列保存入度为0的点,也就是能够输出的点
int q[N];
int d[N];                //保存各个点的入度

void add(int a,int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
int topsort(){
    int hh = 0, tt = -1;
    for(int i=1;i<=n;i++){
        if(!d[i]){
            q[++tt] = i;
        }
    }
    while(hh <= tt){
        int t = q[hh++];
        for(int i = h[t];i != -1;i = ne[i]){
            int j = e[i];
            d[j]--;
            if(d[j] == 0){
                q[++tt] = j;
            }
        }
    }
    return tt == n-1;
}
int main(){
    cin>>n>>m;
    memset(h, -1, sizeof h);
    while(m--){
        int a,b;
        scanf("%d%d",&a,&b);
        d[b]++;
        add(a,b);
    }
    if(topsort()){
        for(int i=0;i<n;i++) printf("%d ",q[i]);
    }
    else puts("-1");
    return 0;
}

树的深度优先遍历 && 树与图的广度优先遍历 && 拓扑排序

图的存储

树的深度优先遍历

树与图的广度优先遍历

拓扑排序

CATALOG

FEATURED TAGS