1.关于二分图的判断:除了黑白染色法，还可以用扩展域并查集。所谓扩展域并查集就是假设每个点可能在集合1中也可能在集合2中，就把点i拆成i和i+n，分别代表在1和在2中的i。如果i和j不在同一集合中，就把i与j+n，以及j与i+n放在同一集合中。这样的好处是无论通过i还是j都可以拿到与它们在同一集合和不在同一集合的点的信息。三个点的情况也是一样的。可以看https://www.luogu.com.cn/problem/P1525
当把u与v连边时，看u与v是否在一个集合中，如在则说明不是二分图，否则把u+N与v放于同一集合，u与v+N放于同一集合
2.有了扩展域并查集，就能用线段树分治做https://www.luogu.com.cn/problem/P5787 了。所谓分治就是把时间作为区间信息放在线段树的节点上，当走入或走出区间时对当前状态进行更新。
3.https://codeforces.com/blog/entry/68138
讲了很多关于dfs树的事情。任何一条回边一定连接dfs树上的一个点和它的后代（而不可能是兄弟或者其他lca不等于这两个点之一的点）
关于dfs树的很好的性质：把边分成dfs边和回边，如果一条dfs边没有回边“跨过”它，那它就是桥。除了tarjan之外还可以用dp[u]求出跨过边(u,fa[u])的回边数量，为0的话(fa[u],u)就是一个桥。
考虑计算dp[u]：我们可以很轻松地统计出有多少回边是从u往上走的,这些回边都跨过了(fa[u],u)，然后考虑来自u的后代的向上的回边，这些回边想跨过(fa[u],u)的话肯定跨过了\((v_i,u)\)，其中v是u的儿子节点，这些边中只达到了u而没能往上走更高的边也跨过不了(fa[u],u)，要把这些边减去。于是得到柿子
然后文章给出了一个例题：判断能不能给无向图的每一条边指定一个方向，使得图仍然强连通（即可从任意点到任意点）。答案是只要没有割边（桥）就可以。这是很好想的，但是构造方案可以很神奇地容易：回边都向上，dfs边都向下即可。
对于仙人掌图，即每个点（在某些定义中也可能是边，二者不等价）属于至多一个环。用dfs树即可通过一个回边和其连接的dfs链得到简单环
对于有向图，除了dfs边和回边之外还可能出现交叉边，这个边连接的x和y满足lca(x,y)!=x&&lca(x,y)!=y,这在无向图中是不存在的
4.最大权闭合子图
解决这样一类问题：给定一个图，每个点有可正可负的边权，现在选一个点集，如果一个点被选，它出发的边指向的点也必须被选，问点集的权的和最大可以是多少。
解决方法是网络流。源点向正权点连容量等于点权的边，负权点向终点连容量等于点权的相反数的边，然后点和点之间根据方向连容量为inf的边，答案为正权点的权值和减去最大流。
可以这么理解:考虑每个正权点，由于是最大流，它会努力把自己必选的点都流满，如果流满后有剩余，那这个剩余的就是选了这个点以及它指向的一系列的点所能提供的收益；如果流不满，它会全部流到终点。从答案上看，这对应得不偿失，不如不选的情况。
5.二分图最大权匹配
考虑使用最大费用最大流，但是最好的匹配的匹配数不一定等于最大匹配数，因此给每个左边的点连一个费用为0的边，这样图的最大流一定是最大匹配，看最大费用即可。
6.一般图最大匹配
https://oiwiki.com/graph/graph-matching/general-match/
7.