今天复习了强联通分量，学习了双联通分量，然而还是不知道什么极大子图是个什么玩意，不过先不管了，好像不重要QAQ，就不管了，所谓双联通强联通，其实主要的区别是图是有向图还是无向图，强联通分量适用于有向图，双联通分量适用于无向图，两者的概念都是可以相互到达。
其中的双联通分量可以细分为：点-双联通分量，边-双联通分量。所谓点-双联通分量是指在一个无向图中两个点中至少有两条路径，且路径中的点（不算头尾）严格不同，不同的点-双联通分量最多有一个公共点，这个点必然是“割顶”，“割顶”的意义为，删除这个点，整个图的联通块数量会增加。至于边-双连通分量是指在一个无向图中两点间至少有两条路径，且路径中的边不同。边-双连通分量中一定没有桥。而桥是指当删去这个边时，连通块的数量会增加。如图
下面上几个模版
判断无向图是否连通
void dfs(int v)
{
node_pointer w;
visited[v] = TRUE;
for(w = graph[v]; w; w = w->link)
{
if(!visited[w->vertex])
{
dfs(w->vertex);
}
}
}
void connect()
{
for(int i = 0; i < n; i++)
{
if(!visited[i])
{
dfs(i);
}
}
}
求点-双联通图
stack<int> s;
int num=1,time=0;
int id[1000]={0};
void tarjan(int x, int fa)
{
dfn[x]=low[x]=time++;
for(int e=first[x];e!=-1;e=next[e])
{
if(x!=fa&&dfn[x]<dfn[v[e]])
{
s.push(e);
if(dfn[x]==0)
{
tarjan(v[e], x);
if(low[v[e]]<low[x]) low[x]=low[v[e]];
if(low[v[e]]>=dfn[x])
{
int edge;
do
{
s.pop();
edge=s.top();
id[u[edge]]=id[v[edge]]=num++;
}while(u[edge]!=x||v[edge]!=v[e]);
}
}
else if(dfn[v[e]]<low[x]) low[x]=dfn[v[e]];
}
}
}
求边-双连通图
void(int u,int fa)
{
dfn[u]=low[u]=++time;
s[top++]=u;
for(int e=first[u];e!=-1;e=next[e])
{
if(v[e]!=fa)
{
if(!dfn[v[e]])
{
tarjan(v[e],u);
if(low[v[e]]<low[u]) low[u]=low[v[e]];
else if(low[v[e]]>dfn[u])
{
for(s[top]=-1;s[top]!=v[e];)
{
id[s[--top]]=num;
num++;
}
}
}
else if(dfn[v[e]]<low[u]) low[u]=dfn[v[e]];
}
}
}
求强联通图
void tarjan(int u)
{
dfn[u] = low[u] = ++ dfs_clock;
vis[u] = inq[u] = true;
s.push(u);
for(int i = head[u] ; i ; i = Edge[i].next)
{
int v = Edge[i].to;
if(!vis[v])
{
tarjan(v);
low[u] = min(low[u],low[v]);
}
else if(inq[v])
low[u] = min(low[u],dfn[v]);
}
if(dfn[u] == low[u])
{
tot++; int t = -1;
while(t!=u)
{
t = s.top();
belong[t] = tot;
inq[t] = 0;
s.pop();
}
}
}
int main()
{
for(int i = 1 ; i <= n ; i++)
if(!vis[i]) tarjan(i);
}
