专题训练3-图论 - C - The Suspects（并查集）
题意2019冠状病毒病（英语：Coronavirus disease 2019，缩写：COVID-19 ），是一种由严重急性呼吸系统综合症冠状病毒2型（缩写：SARS-CoV-2）引发的传染病。此病在全球各国大规模爆发并急速扩散，成为人类历史上致死人数最多的流行病之一。 很显然，目前最好的办法就是将所有可能的患者都隔离起来。 现在某高校正在排查可能的患者，这个高校中有多个社团，每个社团经常进行内部交流，一名学生可能会加入多个社团。学校认为一旦某个社团里出现一名可疑患者，这整个社团的学生都被视为是可能的患者。 现在请你帮忙找到这所学校的所有可能的患者。
（题面漏了一句话：0号学生带病毒。）
输入格式输入文件包含多组数据。
对于每组测试数据：
第一行为两个整数n和m, 其中n是学生的数量, m是社团的数量。0 < n <= 30000，0 <= m <= 500。
接下来m行，每一行有一个整数k，代表社团中学生的数量。之后，有k个整数代表这个社团里每个学生的编号（在0到n-1之间）。
n = m = 0表示输入结束， ...
专题训练3-图论 - L - Cow Contest （Floyd最短路）
题意FJ的N(1 <= N <= 100)头奶牛们最近参加了场程序设计竞赛:)。在赛场上，奶牛们按1..N依次编号。每头奶牛的编程能力不尽相同，并且没有哪两头奶牛的水平不相上下，也就是说，奶牛们的编程能力有明确的排名。 整个比赛被分成了若干轮，每一轮是两头指定编号的奶牛的对决。如果编号为A的奶牛的编程能力强于编号为B的奶牛(1 <= A <= N; 1 <= B <= N; A != B) ，那么她们的对决中，编号为A的奶牛总是能胜出。 FJ想知道奶牛们编程能力的具体排名，于是他找来了奶牛们所有 M(1 <= M <= 4,500)轮比赛的结果，希望你能根据这些信息，推断出尽可能多的奶牛的编程能力排名。比赛结果保证不会自相矛盾。
输入格式第1行: 2个用空格隔开的整数：N 和 M 第2..M+1行: 每行为2个用空格隔开的整数A、B，描述了参加某一轮比赛的奶 牛的编号，以及结果（编号为A，即为每行的第一个数的奶牛为 胜者）
输出格式第1行: 输出1个 ...
G-排解忧伤
12345678910111213141516171819202122232425#include <bits/stdc++.h>using namespace std;int a[100005];int main() { long long n, m, frontier = 0, ans = 0; cin >> n >> m; for (int i = 0; i < m; i++) cin >> a[i]; sort(a, a+m); // 把每个人的心仪座位正序排序 for (int i = 0; i < m; i++) { if (a[i] > frontier) { // 更新边界 frontier = a[i]; } else { ans += frontier-a[i]+1; // 总怒气值增加 frontier++; ...
回溯算法
模板
123456789101112 1 void backtracking(参数) { 2 if (终止条件) { 3 存放结果; 4 return; 5 } 6 7 for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 8 处理节点; 9 backtracking(路径，选择列表); // 递归10 回溯，撤销处理结果;11 }12 }
未优化版本：
1234567891011121314151617181920212223 1 class Solution { 2 private: 3 vector<vector<int>> result; // 存放符合条件结果的集合 4 vector<int> path; // 用来存放符合条件结果 5 void backtracking(int n, int k, int s ...
洛谷P1162 填涂颜色
2021-08-27（22号学长分享的一道题，今天才来记录。）
我自己的DFS解法（有漏洞）：
12345678910111213141516171819202122232425262728293031323334353637383940 1 #include <bits/stdc++.h> 2 using namespace std; 3 int matrix[30][30]; 4 void dfs(int i, int j) { 5 if (matrix[i][j] == 1 || matrix[i][j] == 2) // 是墙，或者走过了，就走人 6 return; 7 if (matrix[i][j] == 0) // 没走过就标记为2 8 matrix[i][j] = 2; 9 10 // 上下左右继续11 dfs(i, j+1);12 dfs(i+1, j);13 dfs(i, j-1);14 dfs(i-1, j);15 return;16 ...
算法笔记：最小生成树
我们把构造连通网的最小代价生成树称为**最小生成树(Minimum Cost Spanning Tree)**。 找连通网的最小生成树，有两种经典的算法，普里姆算法和克鲁斯卡尔算法。
普利姆（Prim）算法
123456789101112131415161718192021222324252627282930313233 1 // Prim算法生成最小生成树 2 void MiniSpanTree_Prim(MGraph G) { 3 int min, i, j, k; 4 int adjvex[MAXVEX]; // 保存相关顶点下标 5 int lowcost[MAXVEX]; // 保存相关顶点间边的权值 6 lowcost[0] = 0; // 初始化第一个权值为0，即v₀加入生成树 7 // lowcost的值为0，在这里就是此下标的顶点已经加入生成树 8 adjvex[0] = 0; // 初始化第一个顶点下标为0 9 for (i = 1; i < G.nu ...
算法笔记：最短路径
迪杰斯特拉（Dijkstra）算法
1234567891011121314151617181920212223242526272829303132333435 1 #define MAXVEX 9 2 #define INFINITY 65535 3 typedef int Pathmatrix[MAXVEX]; // 用于存储最短路径下标的数组 4 typedef int ShortPathTable[MAXVEX]; // 用于存储到各点最短路径的权值和 5 // Dijkstra算法，求有向网G的v0顶点到其余顶点v最短路径P[v]及带权长度D[v] 6 // P[v]的值为前驱顶点下标，D[v]表示v0到v的最短路径长度和 7 void ShortestPath_Dijkstra(MGraph G, int v0, Pathmatrix *P, ShortPathTable *D) { 8 int v, w, k, min; 9 int final[MAXVEX]; // final[w]=1表示求的顶点v0至vw的最短路径10 for (v ...
算法笔记：图的遍历
从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历（Traversing Graph）。
深度优先遍历（Depth_First_Search）
从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。这是连通图的情况，如果是非连通图，只需要对它的连通分量分别进行深度优先遍历，即在先前一个顶点进行一次深度优先遍历后，若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
如果我们用的是邻接矩阵的方式，则代码如下：
123456789101112131415161718 1 typedef bool Boolean; // Boolean是布尔类型，其值是TRUE或FALSE 2 Boolean visited[MAX]; // 访问标志的数组 3 // 邻接矩阵的深度优先递归算法 4 void DFS(MGraph G, int i) { 5 visited[i] = TRUE; 6 printf ...
数据结构笔记：图
各种图定义
图(Graph)是由顶点的有穷非空**集合和顶点之间边的集合组成，通常表示为：G(VE),其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
顶点（Vertex）：图中的数据元素
若顶点vi到vj之间的边没有方向，则称这条边为无向边（Edge），用无序偶对（vi,vj）来表示。
如果图中任意两个顶点之间的边都是无向边，则称该图为**无向图(Undirected graphs)**。
若从顶点v到v的边有方向，则称这条边为有向边，也称为弧（Arc）。用有序偶对<vi,vj>来表示，v1称为弧尾（Tail），v2称为弧头（Head）。
如果图中任意两个顶点之间的边都是有向边，则称该图为有向图（Directed graphs）。
在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向完全图有nx(n-1)/2条边。
在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。含有n个顶点的有向完全图有n×(n-1)条边。
有很少条边或弧的图称为稀疏图，反之称为稠密图。（相对概 ...
数据结构笔记：树
树的抽象数据结构
123456789101112131415161718192021ADT 树（tree）DataOperation InitTree(*T): 构造空树T DestroyTree(*T): 销毁树T CreateTree(*T, definition): 按definition中给出树的定义来构造树 ClearTree(*T): 若树T存在，则将树T清为空树 TreeEmpty(T): 若T为空树，返回true，否则返回false TreeDepth(T): 返回T的深度 Root(T): 返回T的根结点 Value(T, cur_e): cur_e是树T中一个结点，返回此结点的值 Assign(T, cur_e, value): 给树T的结点cur_e赋值为value Parent(T, cur_e): 若cur_e是树T的非根结点，则返回它的双亲，否则返回空 LeftChild(T, cur_e): 若cur_e是树T的非叶结点，则返回它的最左孩子，否则返回空 RightSibling(T, ...