模板【割点和点双连通分量】

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;
}
View Code

 

PART3(算法的延伸应用)

 

PART4(对算法深度的理解)

 

PART5(与其相关的有趣题目)

 

模板【割点和点双连通分量】

上一篇:IOS获取来电去电系统通知达到来电归属地效果(一)


下一篇:Android 遮罩层效果