之前只学了个强连通Tarjan算法，然后又摸了缩点操作；
然后今天在lightoj摸了一道模板题，是求所有桥的题；
然后发现，要把：割点，割点集合，双连通，最小割边集合（桥），点连通分量，边连通分量都学一下。
--------------------
首先这个求割点是在无向图里面实现的（所以看到无向图有点感觉可以往这边考虑吧
先说割点，割点集合：
首先是割点这个问题啊，就是说在一个连通图里面，你删除某个点+这个点所连出去的边，图变成了不连通，就说这个点是割点，
然后呢我再说这句话就好理解了：在一个连通图中,如果有一个点集,删除这个点集+集合中所有点相关联的边,图变成了不连通，就称这个点集为割点集合。
若在连通图上至少删去k个顶点才能破坏图的连通性，则称此图的点连通度为k。
然后说桥；
类似的，如果一个边集，删除这些边（注意是要求删去边集所有边以后）以后，原图连通性被破坏，就称这个点集为割边集合。
一个图的边连通度的定义为最小割边集合中的边数。
当且仅当这个图的边连通度是1，则割边集合的唯一元素被称为桥；
//以下摘自PKU的PDF和 bin神模板
求割点
看了别人的博客：对啊，首先就是暴力一点，根据定义，我遍历所有的点，判断一下图是不是不连通了。
因为暴力所以优化啊。
在深度优先遍历整个图的过程中形成一棵搜索树（思路和有向图求强连通分量类似 ）:
第一种方法：
Dfn[u]定义和Tarjan算法一样，表示编号为i的节点在DFS过程中 的访问序号(也可以叫做开始时间）。
Low[u]定义为u或者u的子树中能够通过非父子边（父子边就是搜索树上的边），追溯到的最早的节点的DFS开始时间；
一个顶点u是割点，当且仅当满足(1)或(2)
(1) 是树根（其实这个根就一个，就是最先进去的点），且u有多于一个子树。
(2) u不为树根，且存在(u,v)为树枝边（或称父子边，即u为v在搜索树中的父亲），使得dfn(u)<=low[v];
我斌模板理解：
const int N=1e4+10;
const int M=2e4+10;
struct Edge{
int to;
int next;
};
Edge q[M*2];
int head[M*2],tol,n,m;
int dfn[N],low[N];
int ind,top;
bool flag[N],vis[N];
void init()
{
tol=0;
memset(head,-1,sizeof(head));
}
void add(int u,int v)
{
q[tol].to=v;
q[tol].next=head[u];
head[u]=tol++;
}
void Tarjan(int u,int pre)
{
int v;
int son=0;
low[u]=dfn[u]=ind++;
vis[u]=true;
for(int i=head[u];i!=-1;i=q[i].next)
{
v=q[i].to;
if(v==pre)
continue;
if(!dfn[v])
{
son++;
Tarjan(v,u);
low[u]=min(low[v],low[u]);
if(u!=pre&&low[v]>=dfn[u])//首先不是树根，且存在(u,v)为树枝边。
flag[u]=true;
}
else
low[u]=min(low[u],dfn[v]);
}
if(pre==u&&son>1)//是树根，且存在两棵子树
flag[u]=true;
}
void qiugedian()
{
//各种初始化；
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(flag,0,sizeof(flag));
ind=1;
Tarjan(1,1); //我们随便设个1作为树根，图上任意点都行，无所谓；
int ans=0;
for(int i=1;i<=n;i++)
if(flag[i])
ans++;
}
下面还是草稿、下次更新桥。。。。
-------------------
第二种方法：
也可以先用Tajan()进行dfs算出所有点的low和dfn值，并记录dfs过程中每个点的父节点，然后再把所有点看一遍，看其low和dfn,以找出割点和桥。
找桥的时候，要注意看有没有重边。有重边，则不是桥。
const int MAXN = 10010;
const int MAXM = 100010;
struct Edge
{
int to,next;
bool cut; //是否为桥的标记
} edge[MAXM];
int head[MAXN],tot;
int Low[MAXN],DFN[MAXN],Stack[MAXN];
int Index,top;
bool Instack[MAXN];
bool cut[MAXN];
int add_block[MAXN];//删除一个点后增加的连通块
int bridge;
void addedge(int u,int v)
{
edge[tot].to = v;
edge[tot].next = head[u];
edge[tot].cut = false;
head[u] = tot++;
}
void Tarjan(int u,int pre)
{
int v;
Low[u] = DFN[u] = ++Index;
Stack[top++] = u;
Instack[u] = true; //入栈标记
int son = 0; //对于节点u的
for(int i = head[u]; i != -1; i = edge[i].next)
{
v = edge[i].to;
if(v == pre) //如果是他的父亲节点
continue;
if(!DFN[v])
{
son++;
Tarjan(v,u);
if(Low[u] > Low[v])
Low[u] = Low[v];
//桥
//一条无向边(u,v)是桥，当且仅当(u,v)为树枝边，且满足DFN(u)<Low(v)。
if(Low[v] > DFN[u])
{
bridge++;
edge[i].cut = true;
edge[i^1].cut = true;
}
//割点
//一个顶点u是割点，当且仅当满足(1)或(2)
//(1) u为树根，且u有多于一个子树
//(2) u不为树根，且满足存在(u,v)为树枝边(或称父子边，即u为v在搜索树中的父亲)，使得DFN(u)<=Low(v)
if(u != pre && Low[v] >= DFN[u])//不是树根
{
cut[u] = true;
add_block[u]++;
}
}
else if( Low[u] > DFN[v])
Low[u] = DFN[v];
}
//树根，分支数大于1
if(u == pre && son > 1) cut[u] = true;
if(u == pre)
add_block[u] = son - 1;
Instack[u] = false;
top--;
}