首页 > 其他分享 >用vector或set建立邻接表

用vector或set建立邻接表

时间:2023-08-27 23:11:29浏览次数:64  
标签:set int 链表 vector 邻接 NULL

用vector或set建立邻接表

在一般情况下使用链表建立的邻接表就行,但若对节点下的子树的顺序有要求的话(树和图的搜索),链表显然不方便,他的顺序在输入时就固定了,所以这时就可以使用vectorset来构建邻接表了

这样也就方便排序了

P5318 【深基18.例3】查找文献 - 洛谷

思路与链表法相同,只是将链表换成vectorset

图
0 1,2
1 3,4
2 NULL
3 NULL
4 5
5 NULL

无权图

vector<int> p[N];

void add(int a, int b) {
    p[a].push_back(b);
}

有权图

链表法是添加一个w[N]数组存权重,这里可以直接用结构体vector

struct node {
	int v, w; // 边的终点编号 权重
};
vector<node> p[N];

void add(int a, int b, int w) {
	p[a].push_back((node){b, w});
}

正如上面洛谷的那道题,他需要有序,用vector存完后排个序就行,但也可以使用set代替vector,省去排序操作,但一般没必要

标签:set,int,链表,vector,邻接,NULL
From: https://www.cnblogs.com/-37-/p/17661069.html

相关文章

  • H. Needle[FFT]或bitset
    Problem-H-Codeforces题意是给三面墙(简化为一条轴),然后给墙上的洞(简化成点),问多少直线可以从第一面墙穿出第三面墙。要使三点共线,那么(b-a)=(c-b)即(a+c)=2*b由于n是1e5所以O(n2)会超时。有两种做法1.本题的任意两数相加的步骤类似多项式乘法,我们把a,c看成两个多项式的系......
  • Doris启动FE时报错:JAVA_HOME tset
    Doris启动FE时报错:JAVA_HOMEtset问题描述运行代码启动fe时报错./start_fe.sh--daemon错误信息Error:JAVA_HOMEisnotset.问题截图问题分析可能服务器环境里安装了多个jdk解决方案在start_fe.sh中输入以下代码,指定jdk即可exportJAVA_HOME=/data/soft/jdk1.8......
  • Codeforces Round 889 (Div. 1) B. Earn or Unlock(dp,bitset)
    题目链接:https://codeforces.com/problemset/problem/1854/B 题目大致题意: 有n张卡牌从上到下堆叠,每张卡片有锁或不锁俩种状态,一开始第一张是不锁的;对最上面的卡牌,如果他是不锁的状态,那么可以进行俩种操作:1:从上到下,将v张被锁的卡牌解锁;2:获取v点能量现在求能获得的最大的......
  • Infinity: Set Theory is the true study of Infinity
    ANINTRODUCTIONTOSETTHEORY-ProfessorWilliamA.R.Weiss,October2,2008Infinity->SetTheory->MathematicsSetTheoryisthetruestudyofInfinity,thisaloneassuresthesubjectofaplaceprominentinhumanculture.Butevenmore,SetT......
  • 为什么@Autowired写在属性上方进行依赖注入时,可以省略setter方法?
    众所周知,spring的依赖注入方式有两种,setter方法注入和构造器注入。但是在实际开发中,即便类的属性没有setter方法,类也没有构造器,只要在属性的上方添加@Autowired注解,这个类属性依然会被自动注入,那么到底是为什么呢?经过上网查询发现,spring其实是从容器查找符合属性类型的对象,通过......
  • 近段时间出现可以用multiset解决的题目
    近段时间出现可以用multiset解决的题目AtCoderBeginnerContest308GMinimumXorPairQuery题意:有一个数组进行\(3\)种操作:加一个数删一个数打印数组\(\min_{1\leqi<j\leqn}{a_i\bigoplusa_j}\)结论:拍序后的数组,其最小异或对在相邻两数中产生那么我......
  • Set(集合)
    Set(集合)set中的值是不能重复的并且这个集合是无序的向set集合中加入值使用add方法127.0.0.1:6379>saddmysethello(integer)1127.0.0.1:6379>saddmysetworld(integer)1127.0.0.1:6379>#####################################查看所有元素127.0.0.1:6379>SMEMBERSmy......
  • Zset(有序集合)
    Zset(有序集合)添加一个和添加多个值127.0.0.1:6379>ZADDmyset1one(integer)1127.0.0.1:6379>ZADDmyset2two3three(integer)2127.0.0.1:6379>ZADDmyset3three3(integer)1127.0.0.1:6379>ZRANGEmyset0-11)"one"2)"two"3)"thr......
  • django 解决queryset惰性机制,实现实时查询
    django在第一次查询后,就把数据进行缓存。如果对数据进行操作后,再进行查询时直接去缓存中取而不去数据库查询,对于想要实时数据时这并不友好。在百度后解决方案如直:classTodayRecordView(viewsets.ModelViewSet):serializer_class=OrderRecordSerializerpagination_c......
  • bitset优化01可行背包
    例题传送门:『STA-R3』Aulvwc先讲bitset用法:1,基础下标:\(5~4~3~2~1~0\)数字:\(0~0~0~0~1~0\)\(bitset\)<\(n\)>\(s\)表示一个\(n\)位的二进制数,空间复杂度:\(O(\frac{n}{32})\),可见其非常优秀因为其跟二进制有关,所以可以使用\(\&,|,\land\)对两个位数相同的\(bitset\)执行按......