iiiiikun
iiiiikun
全部文章
有向图强联通分量
bfs(11)
codeforce(2)
codeforces(49)
dfs(27)
dp(65)
icpc(2)
kmp(2)
kruskal(1)
min25(1)
spfa(3)
stl(3)
三分(1)
二分(11)
二分图(3)
二叉树(2)
二叉树遍历(1)
倍增(1)
几何(1)
前缀和(6)
剪枝(1)
动态规划(2)
单调栈(1)
博弈论(1)
双指针算法(1)
双端队列(1)
唯一分解定理(1)
回文(1)
图论(4)
堆(1)
字符串(2)
尺取法(1)
差分(4)
差分约束(1)
并查集(7)
循环节(1)
快速幂(3)
思维(5)
思维题(6)
拓扑排序(2)
排序(1)
数位dp(3)
数位交换(1)
数学题(1)
数据结构(7)
数论(17)
最大子矩阵(2)
最小生成树(8)
最短路(17)
最长公共上升子序列(1)
未归档(8)
权值线段树(2)
构造(2)
枚举(2)
栈(1)
树形dp(4)
树状数组(3)
树的直径(1)
概率(1)
模拟(1)
模拟赛(1)
模拟退火(1)
模板(9)
欧几里得(1)
欧拉回路欧拉路径(1)
牛客多校(1)
状态压缩(1)
矩形面积(1)
矩阵乘法(1)
矩阵快速幂(1)
离散化(1)
筛素数(1)
线段树(4)
网络流(3)
背包(1)
菜鸟(14)
蓝桥(23)
蓝桥杯(2)
蓝桥训练(2)
贪心(11)
递归(1)
递推(2)
链表(2)
队列(3)
题解(2)
马拉车(2)
高精度(1)
归档
标签
去牛客网
登录
/
注册
iiiiikun的博客
老废物了
全部文章
/ 有向图强联通分量
(共4篇)
174. 受欢迎的牛
当一头牛的出度为0他一定是受欢迎的牛。 #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N=10010,M=50010; int h[...
2020-12-17
0
375
学校网络
题目大致意思:给定一个图,问最少激活多少个点可以遍历整个图,至少加几条边可以让每个点都能到达任何点(成为一个大连通分量)。 第一个问题很简单,只要让入度为0的起点都激活,肯定能遍历所有点,第二个答案是max(起点个数,终点个数),类似于这样,记录规律就行了。。 #include<iostr...
2020-12-17
0
458
最大半连通子图
解题思路:只要找一个最长的链,因为不需要两个点互相到达,只需要一个点能到另一个点就行了,但是这条链不能分叉,先tarjan,缩点,建新图,然后用递推思想,从ssc_cnt开始递减,按照拓扑序做,g[]数组代表以i点为终点的方案数,f[]数组代表以i为终点集合中点的数量。如果f[k]<f[i]+...
2020-12-17
0
589
AcWing 368. 银河
解题报告:这题其实可以差分约束做。但是spfa跑太慢了,我们今天来讲一个线性的做法,tarjan,因为图中没有负点,如果图中存在正环就说明存在和为正数的强联通分量,然后最后问的所有亮度和,可以求出每个连通分量的个数再乘以亮度,亮度可以跑在长路,按照拓扑序的做法。 #include<iostr...
2020-12-17
0
348