PART1(算法思想简介)
1.实现:
2.时间复杂度:
3.特别优势:
4.适用情况:
5.需要注意的点:
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 vBccCnt = 0; bool iscut[N]; set<int> vBcc[N]; stack<edgeK> S; void dfsVBcc(int u, int fa) { dfn[u] = low[u] = ++timeStamp; int child = 0; for(int i = pK[u]; i != -1; i = eK[i].next) { int v = eK[i].v; if(dfn[v] == 0) { S.push(eK[i]); ++child; dfsVBcc(v, u); low[u] = min(low[u], low[v]); if(low[v] >= dfn[u]) //但凡找到一个这样的子树使得此点为割点,就把该子树割出来 { iscut[u] = true; ++vBccCnt; while(true) { edgeK x = S.top(); S.pop(); vBcc[vBccCnt].insert(x.u); vBcc[vBccCnt].insert(x.v); if(x.u == u && x.v == v) { break; } } } } else if(dfn[v] < dfn[u] && v != fa) { S.push(eK[i]); low[u] = min(low[u], dfn[v]); } } if(fa < 0 && child == 1) { iscut[u] = false; } } 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 = vBccCnt = 0; dfsVBcc(1, -1); cout << vBccCnt << endl; for(int i = 1; i <= vBccCnt; ++i) { for(set<int>::iterator it = vBcc[i].begin(); it != vBcc[i].end(); ++it) { cout << (*it) << " "; } cout << endl; } return 0; }
PART3(算法的延伸应用)
PART4(对算法深度的理解)
PART5(与其相关的有趣题目)