4.14~4.19学习总结

图论：强连通分量，双连通分量
主刷题目：缩点、点双连通分量、边双连通分量。

初次思路：遍历整个图，求最大点权和（成功RE）
二次思路：看了一下oi-wiki,考虑求强连通分量，但是没有统计点权之和(全部WA)
三次思路：看了几篇题解，又在oi-wiki上过了一下缩点（SCC：Tarjan）、有向无环图和拓扑排序（DAG），稍微想了一下题目和DAG（有向无环图）的关系，但是因为习惯性地在链式前向星中打了无向图的储存方式，还是没过（AC×7，WA×4）
最终思路:重新把题目过了一遍，看见了题目第一行的$“给定一个 n 个点 m 条边有向图”$，把链式前向星的无向储存改为有向储存（终于AC）

年初在oj里看到的题，然后自己参考着做了（无抄袭）。
思路大概是这样：链式前向星储存无向图，根据点双连通分量的性质利用了割点（因为是点）和$DFS$搜索树中的$dfn$，所以在用链式前向星后以类似于搜索树（Tarjan）的算法求得$DCC$。
因为无法确定单个点的双连通分量个数，也为了防止不必要的空间占用（防止$MLE$），用了动态数组$vector$。 经过几次调试后AC了。

还是年初时在oj看到的题，还是过了一遍知识后参考着做了（还是无抄袭）。
思路：依旧用了链式前向星存无向图，根据边双连通分量的性质利用了桥（因为是边）和$DFS$，为防止MLE开了$vector$，也是调过了已知样例，AC。

总分：175’ / 实际：25’

虽然这次少有的没有爆0，但坏消息是那是道橙题。
得分点在$subtask2$，其他两个$subtask$不是$TLE$就是$AC$,这表明思路没错，错就错在$dfs$超时。
原思路：类似于“能不能跳过去”和“跳过去后又能跳到哪里”，考虑了一下$dfs$或$dp$，但是由于dp太久没用而且推不出动态转移方程，用了dfs。
为了保证$subtask2$的数据能稳过，开了个$O(n^2)$的循环，后来检查代码时发现其实和dfs差不多。
现思路：后来看了下算法标签——“二分”，还是没想出来，去调试第二题去了。

少有的所有$subtask$均没有超时，但是全员$WA$。
原思路：习惯性地用了链式前向星储存数据，并考虑以遍历整个“图”的方式来找到“边权”（即长度）最长的三条边中的四个点。
但是由于遍历时处理不当+调试时间不足，样例都过不了，更不用说代码能过某个$subtask$的一个测试点了……
现思路：重新看题目时，看到了$给定一棵包含 n 个结点的树$，思考了一下源代码中的链式前向星，又转向了查询最大连通边之和的部分。看了几遍题解——“树上遍历”和“要么是菊花图，要么是链”，因为对树形数据结构已经不熟悉，尝试了后者。
可是两次代码不知怎么回事突然“变异”。
一次莫名$RE$（运行着运行着突然崩溃了）。
一次不知怎么回事突然$CE$（在编译器上编译的时候突然蹦到了“后台运行程序”，蹦出了类似于“这个$cmp$函数不能当作函数使用”的$error$，上网搜索了以后发现和网上原因完全不一致）。
总之都没调出来

做作业时基本都能运用，但一到小测就突然“掉线”。思路问题已经减少，更多的是题目解析能力和代码构造能力偏弱，再加上接触“图论”的时间不长及太久没碰C++，一“盲眼”就“踩雷”。
感受很简单：我果然还是太菜了