自己在线制作logo免费网站,wordpress ssl nginx,如何找外包的销售团队,淮北论坛官网app算法提高课笔记 文章目录 理论基础SCC板子 例题受欢迎的牛题意思路代码 学校网络题意思路代码 最大半连通子图题意思路代码 银河题意思路代码 理论基础
什么是连通分量#xff1f;
对于一个有向图#xff0c;分量中任意两点u#xff0c;v#xff0c;必然可以从u走到v
对于一个有向图分量中任意两点uv必然可以从u走到v且从v走到u这样的分量叫做连通分量
如果一个连通分量加上任意一个点都不是连通分量了就把它叫做 强连通分量
强连通分量的主要作用将任意一个有向图转化成一个有向无环图即拓扑图通过缩点的方式缩点就是将所有连通分量缩成一个点
如何求强连通分量呢
按照DFS的顺序搜我们可以将边分为以下四类
树枝边(x, y)x是y的父结点前向边(x, y)x是y的祖先结点后向边(x, y)y是x的祖先结点横叉边往之前搜过的其他点搜 怎么判断一个点是否在强连通分量中
情况一存在后向边指向祖先结点情况二先走到横叉边横叉边再走到祖先结点
反正一定可以走到某个祖先
基于这个想法—— Tarjan 算法求强连通分量SCC
先给每个结点按照 DFS 访问顺序确定一个时间戳时间戳越小说明越先访问到
dfn[u]遍历到 u 的时间戳 low[u]从 u 开始走能遍历到的最小时间戳 id[i]i 所在连通分量的编号
u是其所在强连通分量的最高点 - dfb[u] low[u]
SCC板子
void tarjan(int u)
{dfn[u] low[u] timestamp; // 先将dfn和low都初始化为时间戳stk.push(u), in_stk[u] true; // u加入栈中for (int i h[u]; ~i; i ne[i]){int j e[i]; // 取出u的所有邻点jif (!dfn[j]) // 如果j还没被遍历{tarjan(j);low[u] min(low[u], low[j]); // 用low[j]更新low[u]}else if (in_stk[j]) low[u] min(low[u], dfn[j]); // 如果j已入栈 则用dfn[j]更新low[u]}if (dfn[u] low[u]) // 如果该点是所在强连通分量的最高点{ scc_cnt; // 强连通分量数量加一int y;do {y stk.top(); // 取出栈顶元素stk.pop();in_stk[y] false;id[y] scc_cnt; // 标记每个点所在的连通分量编号} while (y ! u); // 直到取到此连通分量的最高点为止}
}缩点的步骤
遍历所有点 i遍历 i 的所有邻点 j如果 i 和 j 不在同一个连通分量中就加一条新边 id[i]-id[j]
for (int i 1; i n; i )for (int j h[i]; ~j; j ne[j]){int k e[j]; // 遍历i的所有邻点kint a id[i], b id[k]; // 记录ik所在连通分量编号if (a ! b) dout[a] ; // 如果ik不在同一个连通分量 就在两个连通分量之间连一条i指向k的边}做完tarjon后连通分量编号递减的顺序一定就是拓扑序
例题
受欢迎的牛
原题链接
每一头牛的愿望就是变成一头最受欢迎的牛。
现在有 N 头牛编号从 1 到 N给你 M 对整数 (A,B)表示牛 A 认为牛 B 受欢迎。
这种关系是具有传递性的如果 A 认为 B 受欢迎B 认为 C 受欢迎那么牛 A 也认为牛 C 受欢迎。
你的任务是求出有多少头牛被除自己之外的所有牛认为是受欢迎的。
输入格式
第一行两个数 N,M
接下来 M 行每行两个数 A,B意思是 A 认为 B 是受欢迎的给出的信息有可能重复即有可能出现多个 A,B。
输出格式
输出被除自己之外的所有牛认为是受欢迎的牛的数量。
数据范围 1 ≤ N ≤ 104 , 1≤N≤104, 1≤N≤104, 1 ≤ M ≤ 5 × 104 1≤M≤5×104 1≤M≤5×104
输入样例
3 3
1 2
2 1
2 3输出样例
1样例解释
只有第三头牛被除自己之外的所有牛认为是受欢迎的。
题意
一头牛会欢迎另一头牛这种欢迎是有传递性的现给出多对欢迎关系问有几头牛是被其余所有牛欢迎的
思路
先对连通分量进行缩点操作
之后分析如果有唯一一个连通分量满足出度为0那么这个连通分量内的所有点都可以由其余任意点到达答案就是这个连通分量内点的个数如果这样的连通分量超过一个就不满足条件
代码
#include bits/stdc.husing namespace std;const int N 10010, M 50010;int n, m;
int h[N], ne[M], e[M], idx;
int dfn[N], low[N], timestamp;
stackint stk;
bool in_stk[N]; // 存储点是否入栈
int id[N], scc_cnt, Size[N];
int dout[N]; // 连通分量的出度void add(int a, int b)
{e[idx] b, ne[idx] h[a], h[a] idx ;
}void tarjan(int u)
{dfn[u] low[u] timestamp; // 先将dfn和low都初始化为时间戳stk.push(u), in_stk[u] true; // u加入栈中for (int i h[u]; ~i; i ne[i]){int j e[i]; // 取出u的所有邻点jif (!dfn[j]) // 如果j还没被遍历{tarjan(j);low[u] min(low[u], low[j]); // 用low[j]更新low[u]}else if (in_stk[j]) low[u] min(low[u], dfn[j]); // 如果j已入栈 则用dfn[j]更新low[u]}if (dfn[u] low[u]) // 如果该点是所在强连通分量的最高点{ scc_cnt; // 强连通分量数量加一int y;do {y stk.top(); // 取出栈顶元素stk.pop();in_stk[y] false;id[y] scc_cnt; // 标记每个点所在的连通分量编号Size[scc_cnt] ; // 更新此连通分量中的点个数} while (y ! u); // 直到取到此连通分量的最高点为止}
}int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin n m;memset(h, -1, sizeof h);while (m -- ){int a, b;cin a b;add(a, b);}for (int i 1; i n; i )if (!dfn[i]) tarjan(i);for (int i 1; i n; i )for (int j h[i]; ~j; j ne[j]){int k e[j]; // 遍历i的所有邻点kint a id[i], b id[k]; // 记录ik所在连通分量编号if (a ! b) dout[a] ; // 如果ik不在同一个连通分量 就在两个连通分量之间连一条i指向k的边}int zeros 0, sum 0;for (int i 1; i scc_cnt; i )if (!dout[i]) // 如果当前连通分量出度为0{zeros ; // 出度为0的连通分量个数加一sum Size[i]; // 更新出度为0的连通分量中点的个数if (zeros 1) // 如果出度为0的连通分量个数超过一个 说明没有一头牛被所有牛喜欢{sum 0;break;}}cout sum \n;
}学校网络
原题链接
一些学校连接在一个计算机网络上学校之间存在软件支援协议每个学校都有它应支援的学校名单学校 A 支援学校 B并不表示学校 B 一定要支援学校 A。
当某校获得一个新软件时无论是直接获得还是通过网络获得该校都应立即将这个软件通过网络传送给它应支援的学校。
因此一个新软件若想让所有学校都能使用只需将其提供给一些学校即可。
现在请问最少需要将一个新软件直接提供给多少个学校才能使软件能够通过网络被传送到所有学校
最少需要添加几条新的支援关系使得将一个新软件提供给任何一个学校其他所有学校就都可以通过网络获得该软件
输入格式
第 1 行包含整数 N表示学校数量。
第 2…N1 行每行包含一个或多个整数第 i1 行表示学校 i 应该支援的学校名单每行最后都有一个 0 表示名单结束只有一个 0 即表示该学校没有需要支援的学校。
输出格式
输出两个问题的结果每个结果占一行。
数据范围 2 ≤ N ≤ 100 2≤N≤100 2≤N≤100
输入样例
5
2 4 3 0
4 5 0
0
0
1 0输出样例
1
2题意
给出一张图
问题一至少从多少个点出发能够遍历完图上所有点问题二至少加多少条边能让图的强连通分量就是自身
思路
设入度为0的连通分量个数为a出度为0的连通分量个数为b
问题一就是问a的大小
问题二就是问ab中较大的值需要特判一下如果只有一个强连通分量就不需要加边输出0即可 举个栗子 不具体证明了
代码
#include bits/stdc.husing namespace std;const int N 110, M 10010;int n, m;
int h[N], ne[M], e[M], idx;
int dfn[N], low[N], timestamp;
stackint stk;
bool in_stk[N]; // 存储点是否入栈
int id[N], scc_cnt;
int din[N], dout[N]; // 连通分量的入度和出度void add(int a, int b)
{e[idx] b, ne[idx] h[a], h[a] idx ;
}void tarjan(int u)
{dfn[u] low[u] timestamp; // 先将dfn和low都初始化为时间戳stk.push(u), in_stk[u] true; // u加入栈中for (int i h[u]; ~i; i ne[i]){int j e[i]; // 取出u的所有邻点jif (!dfn[j]) // 如果j还没被遍历{tarjan(j);low[u] min(low[u], low[j]); // 用low[j]更新low[u]}else if (in_stk[j]) low[u] min(low[u], dfn[j]); // 如果j已入栈 则用dfn[j]更新low[u]}if (dfn[u] low[u]) // 如果该点是所在强连通分量的最高点{ scc_cnt; // 强连通分量数量加一int y;do {y stk.top(); // 取出栈顶元素stk.pop();in_stk[y] false;id[y] scc_cnt; // 标记每个点所在的连通分量编号} while (y ! u); // 直到取到此连通分量的最高点为止}
}int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin n;memset(h, -1, sizeof h);for (int i 1; i n; i ) // 建图{int t;while (cin t, t) add(i, t);}for (int i 1; i n; i )if (!dfn[i]) tarjan(i);for (int i 1; i n; i )for (int j h[i]; ~j; j ne[j]){int k e[j]; // 遍历i的所有邻点kint a id[i], b id[k]; // 记录ik所在连通分量编号if (a ! b) // 如果ik不在同一个连通分量 就在两个连通分量之间连一条i指向k的边{dout[a] ;din[b] ;}}int a 0, b 0;for (int i 1; i scc_cnt; i ){if (!din[i]) a ; // 记录入度为0的点个数if (!dout[i]) b ; // 记录出度为0的点个数}cout a \n;if (scc_cnt 1) cout 0 \n;else cout max(a, b) \n;
}最大半连通子图
原题链接
一个有向图 G(V,E) 称为半连通的 (Semi-Connected)如果满足∀u,v∈V满足 u→v 或 v→u即对于图中任意两点 u,v存在一条 u 到 v 的有向路径或者从 v 到 u 的有向路径。
若 G′(V′,E′) 满足E′ 是 E 中所有和 V′ 有关的边则称 G′ 是 G 的一个导出子图。
若 G′ 是 G 的导出子图且 G′ 半连通则称 G′ 为 G 的半连通子图。
若 G′ 是 G 所有半连通子图中包含节点数最多的则称 G′ 是 G 的最大半连通子图。
给定一个有向图 G请求出 G 的最大半连通子图拥有的节点数 K以及不同的最大半连通子图的数目 C。
由于 C 可能比较大仅要求输出 C 对 X 的余数。
输入格式
第一行包含三个整数 N,M,X。N,M 分别表示图 G 的点数与边数X 的意义如上文所述
接下来 M 行每行两个正整数 a,b表示一条有向边 (a,b)。
图中的每个点将编号为 1 到 N保证输入中同一个 (a,b) 不会出现两次。
输出格式
应包含两行。
第一行包含一个整数 K第二行包含整数 C mod X。
数据范围 1 ≤ N ≤ 105 , 1≤N≤105, 1≤N≤105, 1 ≤ M ≤ 106 , 1≤M≤106, 1≤M≤106, 1 ≤ X ≤ 108 1≤X≤108 1≤X≤108
输入样例
6 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4输出样例
3
3题意
找出最大的半连通子图输出节点数和子图个数
思路
最大半连通子图就是图上最长的一条链所以按照以下思路
tarjan缩点、建图、给边判重按拓扑序递推
代码
#include bits/stdc.husing namespace std;typedef long long ll;const int N 100010, M 2000010;int n, m, mod;
int h[N], hs[N], ne[M], e[M], idx;
int dfn[N], low[N], timestamp;
stackint stk;
bool in_stk[N]; // 存储点是否入栈
int id[N], scc_cnt, scc_size[N];
int f[N], g[N]; // 连通分量的入度和出度void add(int h[], int a, int b)
{e[idx] b, ne[idx] h[a], h[a] idx ;
}void tarjan(int u)
{dfn[u] low[u] timestamp; // 先将dfn和low都初始化为时间戳stk.push(u), in_stk[u] true; // u加入栈中for (int i h[u]; ~i; i ne[i]){int j e[i]; // 取出u的所有邻点jif (!dfn[j]) // 如果j还没被遍历{tarjan(j);low[u] min(low[u], low[j]); // 用low[j]更新low[u]}else if (in_stk[j]) low[u] min(low[u], dfn[j]); // 如果j已入栈 则用dfn[j]更新low[u]}if (dfn[u] low[u]) // 如果该点是所在强连通分量的最高点{ scc_cnt; // 强连通分量数量加一int y;do {y stk.top(); // 取出栈顶元素stk.pop();in_stk[y] false;id[y] scc_cnt; // 标记每个点所在的连通分量编号scc_size[scc_cnt] ;} while (y ! u); // 直到取到此连通分量的最高点为止}
}int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);memset(h, -1, sizeof h);memset(hs, -1, sizeof hs);cin n m mod;while (m -- ){int a, b;cin a b;add(h, a, b);}for (int i 1; i n; i )if (!dfn[i]) tarjan(i);unordered_setll S;for (int i 1; i n; i )for (int j h[i]; ~j; j ne[j]){int k e[j]; // 遍历i的所有邻点kint a id[i], b id[k]; // 记录ik所在连通分量编号ll hash a * 1000000ll b;if (a ! b !S.count(hash)) // 如果ik不在同一个连通分量 就在两个连通分量之间连一条i指向k的边{add(hs, a, b);S.insert(hash);}}for (int i scc_cnt; i; i -- ){if (!f[i]) // 起点{f[i] scc_size[i]; // 更新最大半连通子图内元素个数g[i] 1; // 更新最大半连通子图个数}for (int j hs[i]; ~j; j ne[j]){int k e[j];if (f[k] f[i] scc_size[k]) // 有更优解{f[k] f[i] scc_size[k];g[k] g[i];}else if (f[k] f[i] scc_size[k]) // 有结果一样的解g[k] (g[k] g[i]) % mod;}}int maxf 0, sum 0;for (int i 1; i scc_cnt; i )if (f[i] maxf){maxf f[i];sum g[i];}else if (f[i] maxf) sum (sum g[i]) % mod;cout maxf \n;cout sum \n;
}银河
原题链接
银河中的恒星浩如烟海但是我们只关注那些最亮的恒星。
我们用一个正整数来表示恒星的亮度数值越大则恒星就越亮恒星的亮度最暗是 1。
现在对于 N 颗我们关注的恒星有 M 对亮度之间的相对关系已经判明。
你的任务就是求出这 N 颗恒星的亮度值总和至少有多大。
输入格式
第一行给出两个整数 N 和 M。
之后 M 行每行三个整数 T,A,B表示一对恒星 (A,B) 之间的亮度关系。恒星的编号从 1 开始。
如果 T1说明 A 和 B 亮度相等。如果 T2说明 A 的亮度小于 B 的亮度。如果 T3说明 A 的亮度不小于 B 的亮度。如果 T4说明 A 的亮度大于 B 的亮度。如果 T5说明 A 的亮度不大于 B 的亮度。
输出格式
输出一个整数表示结果。
若无解则输出 −1。
数据范围 N ≤ 100000 , M ≤ 100000 N≤100000,M≤100000 N≤100000,M≤100000
输入样例
5 7
1 1 2
2 3 2
4 4 1
3 4 5
5 4 5
2 3 5
4 5 1 输出样例
11题意
求图中有无正环的问题
思路
用tarjan求强连通分量缩点、根据差分约束建图依据拓扑序递推
代码
#include bits/stdc.husing namespace std;typedef long long ll;const int N 100010, M 600010;int n, m;
int h[N], hs[N], w[M], ne[M], e[M], idx;
int dfn[N], low[N], timestamp;
stackint stk;
bool in_stk[N]; // 存储点是否入栈
int id[N], scc_cnt, scc_size[N];
int dist[N]; // 连通分量的入度和出度void add(int h[], int a, int b, int c)
{e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx ;
}void tarjan(int u)
{dfn[u] low[u] timestamp; // 先将dfn和low都初始化为时间戳stk.push(u), in_stk[u] true; // u加入栈中for (int i h[u]; ~i; i ne[i]){int j e[i]; // 取出u的所有邻点jif (!dfn[j]) // 如果j还没被遍历{tarjan(j);low[u] min(low[u], low[j]); // 用low[j]更新low[u]}else if (in_stk[j]) low[u] min(low[u], dfn[j]); // 如果j已入栈 则用dfn[j]更新low[u]}if (dfn[u] low[u]) // 如果该点是所在强连通分量的最高点{ scc_cnt; // 强连通分量数量加一int y;do {y stk.top(); // 取出栈顶元素stk.pop();in_stk[y] false;id[y] scc_cnt; // 标记每个点所在的连通分量编号scc_size[scc_cnt] ;} while (y ! u); // 直到取到此连通分量的最高点为止}
}int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);memset(h, -1, sizeof h);memset(hs, -1, sizeof hs);cin n m;for (int i 1; i n; i ) add(h, 0, i, 1);while (m -- ){int t, a, b;cin t a b;if (t 1) add(h, b, a, 0), add(h, a, b, 0);else if (t 2) add(h, a, b, 1);else if (t 3) add(h, b, a, 0);else if (t 4) add(h, b, a, 1);else add(h, a, b, 0);}tarjan(0);bool success true;for (int i 0; i n; i ){for (int j h[i]; ~j; j ne[j]){int k e[j]; // 遍历i的所有邻点kint a id[i], b id[k]; // 记录ik所在连通分量编号if (a b) // ik在同一个强连通分量{if (w[j] 0) // ik间有权值为正的路径{success false; // 无解break;}}else add(hs, a, b, w[j]);// 如果ik不在同一个连通分量 就在两个连通分量之间连一条i指向k的边}if (!success) break;}if (!success) cout -1\n;else // 有解则求最长路{for (int i scc_cnt; i; i -- ){for (int j hs[i]; ~j; j ne[j]){int k e[j];dist[k] max(dist[k], dist[i] w[j]);}}ll res 0;for (int i 1; i scc_cnt; i ) res (ll)dist[i] * scc_size[i];cout res \n;}
}
