没有写题解。补一波
问题1：求有向图中入度为0的点个数
问题2：使得整个图变成一个联通分量
问题1直接缩点统计
问题2=max(入度为0的点，出度为0的点），注意原始图是一个联通分量的情况
统计割点的个数。
割点的两种情况
统计有向图桥的数量
有向图桥在树枝边是判断一下
往无向图的边中增加边，同时输出此时桥的数量
缩点后，进行暴力的并查集
void link(int x,int y) { int fa1=find(x),fa2=find(y); if (dfn[fa1]<dfn[fa2]) fa[fa2]=fa1; else fa[fa1]=fa2; } while (p--) { scanf("%d %d",&j,&k); j=find(j); k=find(k); while (j!=k) { ans--; if (dfn[j]<dfn[k]) { link(k,pre[k]); k=find(k); } else { link(j,pre[j]); j=find(j); } } printf("%d ",ans); } }
缩点后求图的最长边
HDU - 4635 Strongly connected
添加尽可能多的边使得图不强联通
反向考虑，先让图强连通，再删边，算了下是个二次函数，也就是尽量把图分成大小差距很大的两块。
转化为找入度为0的最小联通块和出度为0的最小联通块。
二分图匹配的可行边（不影响答案）
匹配后，一边的点连向他的match[]，然后跑tarjan，如果在一个联通分量说明可以随便换，
那就判断与它相连的另一个点是否在同一个联通分量里面。
当然还有增加虚点的操作
找无向图桥边，依然判断桥边只需在树枝边时判断