_kirito__

图论

Codeforces(2) Contest(3) STL(1) 二分(2) 前缀和(2) 动态规划(2) 并查集(3) 搜索(3) 操作系统(1) 数位dp(2) 杂项(2) 模拟(1) 线段树(5) 题解(1)

/ 注册

全部文章 / 图论（共4篇）

DFS序

DFS序我们在处理一些树上计数问题时，经常由于数据量过大而树形结构的统计操作又十分复杂，所以常常需要将树形结构转换成更加便于查询和修改的线性结构，再结合树状数组或者线段树等高效的查询更新结构来解决问题，这时，为了将树形结构转换成线性结构，我们经常会用到的一个东西就是DFS序。想要得到DFS序...

2020-04-19

0 373

邻接表

邻接表在图的描述中，经常会用到邻接表，有时我们会用到邻接矩阵来保存图的边和权值等信息，但是这回产生\(N^2\)的空间复杂度，在数据量比较大的多数情况下，我们是无法存储的，所以这是就需要用到空间复杂度为\(N\)的邻接表来存储图。存储对于邻接表的存储方式，我们除了保存边的三个数组\(u,...

2020-04-19

0 362

Line++

Line++ Problem Statement We have an undirected graph GG with NN vertices numbered 11 to NN and NN edges as follows: For each i=1,2,...,N−1, ther...

2020-04-07

0 443

可达？

可达？题目描述小明有一张N个点M条边的有向无环图，他想知道从每个点出发能够到达的点的数量。N,M≤30000。输入第一行两个整数N,M，接下来M行每行两个整数x,y，表示从x到y的一条有向边。输出共N行，表示每个点能够到达的点的数量。样例输入...

2020-02-29

0 334