PART1（算法思想简介）
1.实现：
2.时间复杂度：
O (V+E)
3.特别优势：
4.适用情况：
5.需要注意的点：1.割点属于VBcc，但是桥不属于eBcc
2.边双连通分量至少得有一条边（这是根据算法推出得，因为只有一个点的跟没有被算作一个边双连通分量）
6:函数、变量名的解释+英文：
bcc（Biconnected component）（双连通分量）
边双联通 eBcc
点双连通 vBcc
int timeStamp（时间戳）
int dfn[i]（访问到i时的时间戳）
int low[i]（i及其子结点所能访问到的最小的时间戳）
bool iscut[i]（i是否为割点）
set<int> eBcc[i]（存储第i个ebcc上的点）
set<int> vBcc[i]（存储第i个vbcc上的点）
stack<edgeK> S（存储经过的边）
PART2（算法各种类型（并附上代码））
可用代码
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<iomanip>
#include<iostream>
#include<stack>
using namespace std;
#define inf 0x3f3f3f3f
const int N = 1e2+10;
const int M = 1e4+10;
//与边相关
struct edgeK
{
int u, v, next, w;
} eK[M];
int pK[N], eidK;
inline void InitEdgeK()
{
memset(pK, -1, sizeof(pK));
eidK = 0;
}
inline void InsertK(int u, int v, int w = 0)
{
eK[eidK].next = pK[u];
eK[eidK].u = u;
eK[eidK].v = v;
eK[eidK].w = w;
pK[u] = eidK++;
}
//缩点
int timeStamp = 0;
int dfn[N], low[N];
int eBccCnt = 0;
bool iscut[N];
set<int> eBcc[N];
stack<edgeK> S;
void DfsEBcc(int u, int fa)
{
dfn[u] = low[u] = ++timeStamp;
for(int i = pK[u]; i != -1; i = eK[i].next)
{
int v = eK[i].v;
if(dfn[v] == 0)
{
S.push(eK[i]);
DfsEBcc(v, u);
low[u] = min(low[u], low[v]);
if(low[v] > dfn[u])
{
++eBccCnt;
while(true)
{
edgeK x = S.top();
S.pop();
if(x.u == u && x.v == v)
{
break;
}
eBcc[eBccCnt].insert(x.u);
eBcc[eBccCnt].insert(x.v);
}
}
}
else if(dfn[v] < dfn[u] && v != fa)
{
S.push(eK[i]);
low[u] = min(low[u], dfn[v]);
}
}
if(fa < 0 && !S.empty())
{
++eBccCnt;
while(!S.empty())
{
edgeK x = S.top();
S.pop();
eBcc[eBccCnt].insert(x.u);
eBcc[eBccCnt].insert(x.v);
}
}
}
int main()
{
//freopen("in.txt","r", stdin);
//freopen("out.txt","w", stdout);
ios::sync_with_stdio(false);
InitEdgeK();
int n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i)
{
int u, v;
cin >> u >> v;
InsertK(u, v);
InsertK(v, u);
}
memset(dfn, 0, sizeof(dfn));
timeStamp = eBccCnt = 0;
DfsEBcc(1, -1);
cout << eBccCnt << endl;
for(int i = 1; i <= eBccCnt; ++i)
{
for(set<int>::iterator it = eBcc[i].begin(); it != eBcc[i].end(); ++it)
{
cout << (*it) << " ";
}
cout << endl;
}
return 0;
}
/*
4 4
1 2
2 3
3 4
4 2
*/
View Code
PART3（算法的延伸应用）
PART4（对算法深度的理解）