首页 > 其他分享 >通关搜索和图论 day_13 -- 树和图的深搜和宽搜和拓扑排序

通关搜索和图论 day_13 -- 树和图的深搜和宽搜和拓扑排序

时间:2023-01-05 19:56:42浏览次数:74  
标签:树和图 13 idx -- ne int include 节点

树和图的存储

树是一种特殊的图,无环连通图

图分为有向图和无向图

如果是无向图就建立两个边 a -> b && b -> a ,所有无向图就是特殊的有向图

邻接矩阵 g[a,b] 记录 a -> b 如果有权重,其值就是权重,没有权重这个值就是一个 布尔值,true代表有边,邻接矩阵不能存储重边

邻接表 每个点上都是一个单链表,每个单链表存储每个点能走到哪些点

graph TD 1-->4 1-->3 3-->4 2-->1 2-->4

如图所示的图一共有四个点,所以开 4 个单链表

1:--> 3 --> 4 --> 空

2:--> 1 --> 4 --> 空

3:--> 4 --> 空

4:--> 空

单链表中点的次序不重要

此时我们插入一条 2 --> 3 的点

那么就找到 2 这个单链表 然后把 3 插入这个单链表,一般选择是头插

也可以用 vector 来模拟邻接表

模板

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

const int N = 100010 , M = N * 2;
// h存的 N 个链表的链表头,e存的是我们所有结点的值是多少,ne存的是每个结点的 next值是多少
int h[N],e[M],ne[M],idx;


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

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    //初始化
    memset(h,-1,sizeof h);
    
    return 0;
}

树和图的深度优先遍历

模板

void dfs(int u)
{
    st[u] = true    // u 已经被遍历了
    for(int i = h[u];i != -1;i = ne[i])
    {
        int j = e[i];   // 定的图里的编号是多少
        if(!st[j])
        {
            dfs(j);
        }
    }
}

例题

846. 树的重心 - AcWing题库

给定一颗树,树中包含 n 个结点(编号 1∼n)和 n−1 条无向边。

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

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

输入格式

第一行包含整数 n,表示树的结点数。

接下来 n−1行,每行包含两个整数 a 和 b,表示点 a和点 b 之间存在一条边。

输出格式

输出一个整数 m,表示将重心删除后,剩余各个连通块中点数的最大值。

数据范围

1≤n≤105

输入样例

9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6

输出样例:

4

例如我有如下树

graph TD 1-->2 1-->4 1-->7 2-->8 2-->5 4-->3 4-->6 3-->9

此时如果我把 1 删除后,剩下三个连通块分别为

graph TD 7 2-->8 2-->5 4-->3 4-->6 3-->9

那么最大点数为 4 ,如果删掉 2

graph TD 1-->4 1-->7 8 5 4-->3 4-->6 3-->9

最大的点树就是 6

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

const int N = 1e5 + 10; //数据范围是10的5次方
const int M = 2 * N; //以有向图的格式存储无向图,所以每个节点至多对应2n-2条边

int h[N]; //邻接表存储树,有n个节点,所以需要n个队列头节点
int e[M]; //存储元素
int ne[M]; //存储列表的next值
int idx; //单链表指针
int n; //题目所给的输入,n个节点
int ans = N; //表示重心的所有的子树中,最大的子树的结点数目

bool st[N]; //记录节点是否被访问过,访问过则标记为true


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

// 返回以 u 为根的子树的大小
int dfs(int u) {
    int res = 0; //存储 删掉某个节点之后,最大的连通子图节点数
    st[u] = true; //标记访问过u节点
    int sum = 1; //存储 以u为根的树 的节点数, 包括u,如图中的4号节点

    //访问u的每个子节点
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        //因为每个节点的编号都是不一样的,所以 用编号为下标 来标记是否被访问过
        if (!st[j]) {
            int s = dfs(j);  // u节点的单棵子树节点数 如图中的size值
            res = max(res, s); // 记录最大联通子图的节点数
            sum += s; //以j为根的树 的节点数
        }
    }

    //n-sum 如图中的n-size值,不包括根节点4;
    res = max(res, n - sum); // 选择u节点为重心,最大的 连通子图节点数
    ans = min(res, ans); //遍历过的假设重心中,最小的最大联通子图的 节点数
    return sum;
}


int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    memset(h,-1,sizeof h);
    cin >> n;
    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;
}

树和图的宽度优先遍历

模板

queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (q.size())
{
    int t = q.front();
    q.pop();

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

例题

847. 图中点的层次 - AcWing题库

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

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

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

输入格式

第一行包含两个整数 n 和 m。

接下来 m 行,每行包含两个整数 a 和 b,表示存在一条从 a 走到 b 的长度为 1 的边。

输出格式

输出一个整数,表示 1 号点到 n 号点的最短距离。

数据范围

1≤n,m≤105

输入样例:

4 5
1 2
2 3
3 4
1 3
1 4

输出样例:

1

我第一次发散到这个点的时候,就是我到这个点的最短路径

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 100010;

int n,m;
int h[N],e[N],ne[N],idx;
int d[N],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; //0号节点是编号为1的节点
    memset(d,-1,sizeof d);
    d[1]=0; //存储每个节点离起点的距离
    //当我们的队列不为空时
    while(hh<=tt)
    {
        //取出队列头部节点
        int t=q[hh++];
        //遍历t节点的每一个邻边
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            //如果j没有被扩展过
            if(d[j]==-1)
            {
                d[j]=d[t]+1; //d[j]存储j节点离起点的距离,并标记为访问过
                q[++tt] = j; //把j结点 压入队列
            }
        }
    }
    return d[n];
}


int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    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;
}

拓扑排序

有向图才会有拓扑序列

比方说有图如下

graph TD 1-->2 2-->3 1-->3

1--2--3 就是一个拓扑序列

拓扑序列要求 对于每条边 起点都要在终点前面,并不是每一个图都有拓扑序

比方说

graph TD 1-->2 2-->3 3-->1

所以 有向无环图 又被称为拓扑图

每个点有入度和出度,入度就是有多少条边指向自己,出度就是自己指向多少条边

入度为 0 就代表不会有任何一条边要求在我前面

模板

bool topsort()
{
    int hh = 0, tt = -1;

    // d[i] 存储点i的入度
    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];
            if (-- d[j] == 0)
                q[ ++ tt] = j;
        }
    }

    // 如果所有点都入队了,说明存在拓扑序列;否则不存在拓扑序列。
    return tt == n - 1;
}

例题

848. 有向图的拓扑序列 - AcWing题库

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

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

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

输入格式

第一行包含两个整数 n 和 m。

接下来 mm 行,每行包含两个整数 x 和 y,表示存在一条从点 x 到点 y 的有向边 (x,y)。

输出格式

共一行,如果存在拓扑序列,则输出任意一个合法的拓扑序列即可。

否则输出 −1。

数据范围

1≤n,m≤105

输入样例:

3 3
1 2
2 3
1 3

输出样例:

1 2 3
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 100010;

int  n,m;
int h[N],e[N],ne[N],idx;
int q[N],d[N];

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

bool 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.tie(0);
    ios::sync_with_stdio(false);
    
    cin >> n >> m;
    memset(h,-1,sizeof h);
    
    for(int i = 0;i < m;i++)
    {
        int a,b;
        cin >> a >> b;
        add(a,b);
        d[b]++;
    }
    
    if(topsort())
    {
        for(int i = 0;i< n;i++)
        {
            cout << q[i] << " ";
        }
    }else{
        cout << "-1" << endl;
    }
}

标签:树和图,13,idx,--,ne,int,include,节点
From: https://www.cnblogs.com/ShibuyaKanon/p/17028713.html

相关文章

  • librosa.filters.mel
    @deprecate_positional_args@cache(level=10)defmel(*,sr,n_fft,n_mels=128,fmin=0.0,fmax=None,htk=False,norm="slaney",......
  • URAL2124 - Algebra on Segment
    题意维护一个序列,支持区间乘\(x\),和查询区间的\(Span\)的大小。一个集合的\(Span\)定义为可以表示成其中若干可重复整数的乘积的数的集合。所有计算在模\(p\)意义......
  • 剑指offer解析
    一、整数篇整数的除法整数除法的结果应当截去(truncate)其小数部分,例如:truncate(8.345)=8 以及 truncate(-2.7335)=-2假设我们的环境只能存储32位有符号整数,其......
  • 电商项目功能测试全流程
    项目管理软件项目管理软件-禅道的介绍禅道环境搭建熟悉禅道的bug管理流程测试前的准备被测系统业务逻辑梳理测试计划与方案设计思路编写软件......
  • Gc 原理
    三色标记并不能并发或者增量,需要STW来保证正确性,想要在并发或者增量的标记算法中保证正确性,我们需要达成以下两种三色不变性(强弱三色不变性),采取写屏障来满足......
  • cuda gdb文档翻译
    3-gettingstarted3.1设置cuda-gdb的调试环境3.1.1临时文件存放位置Bydefault,CUDA-GDBuses/tmpasthedirectorytostoretemporaryfiles.Toselectadif......
  • 发送邮箱出现报错:"smtp.exmail.qq.com"port 465, isSSL false
    1、问题:使用邮箱时,出现报错"smtp.exmail.qq.com"port465,isSSLfalse这个使用465端口才会出现这个错误,但是使用25端口就不会出现这个错误 2、分析原因:从网上看是因为......
  • NC20284 [SCOI2011]糖果
    题目链接题目题目描述幼儿园里有N个小朋友,lxhgww老师现在想要给这些小朋友们分配糖果,要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心,总是会提出一些要求,比如小明......
  • Clickhouse优缺点及性能情况
    优点:1,为了高效的使用CPU,数据不仅仅按列存储,同时还按向量进行处理;2,数据压缩空间大,减少IO;处理单查询高吞吐量每台服务器每秒最多数十亿行;3,索引非B树结构,不需要满足最左原......
  • 文件及目录操作
     一、实验目的和要求1、学会基本文件操作;2、学会目录操作;3、学会高级文件操作。二、实验环境软件版本:Python3.1064_bit三、实验过程1、实例1:创建并打开记录蚂......