精华内容
下载资源
问答
  • 连通分量

    2019-10-06 16:39:55
    连通分量是指有向图的一个极大子图使得其中每个点都可以到达其他所有点。 双连通分量是指无向图中的一个极大子图,分为两种: 点双连通分量:至少删去两个点才能使子图不连通 边双连通分量:至少删去两条边才能使...

    定义

    强连通分量是指有向图的一个极大子图使得其中每个点都可以到达其他所有点。

    双连通分量是指无向图中的一个极大子图,分为两种:

    • 点双连通分量:至少删去两个点才能使子图不连通
    • 边双连通分量:至少删去两条边才能使子图不连通

    图的连通性问题一般都有对应的Tarjan算法求解,一个著名的例子就是支配树的Lengauer-Tarjan算法。这里要讲的是连通分量的Tarjan算法。

    Tarjan算法

    Tarjan算法基于dfs搜索树。定义\(dfn[x]\)\(x\)被搜索的时间,再定义一个\(low[x]\),表示\(x\)能绕回的祖先中\(dfn\)值最小的那个。\(low\)数组的求解是十分简单的。对于树枝边,并不会绕回到祖先去,所以\(low[x]=min(low[x],low[v])\);对于后向边,\(low[x]=min(low[x],dfn[v])\)

    强连通分量

    每搜索一个点,我们都把它加进栈里。如果搜索完\(x\)的所有连边后发现\(dfn[x]=low[x]\),那么它与当前在栈内的所有点构成了一个强连通分量。

    双连通分量

    点双连通分量

    深搜的过程中,我们把放进栈中,如果搜到的是后向边,那么更新当前点的\(low\)值。如果是树边,那么搜完之后,若\(dfn[u]\le low[v]\)即从下面无法走回到当前点之前的点,那么栈中之前压入的边和上面的边包含的点就组成了一个点双连通分量。

    边双连通分量

    深搜的过程中,如果搜完一条树枝边后发现\(dfn[u]<low[v]\),那么这条边就是原图的一个桥。把全部桥搜出来后断掉它们,现在的每个连通图都是一个边双连通分量。

    双连通分量代码

    #include<cstdio>
    #include<cctype>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    using namespace std;
    int read() {
        int x=0,f=1;
        char c=getchar();
        for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
        for (;isdigit(c);c=getchar()) x=x*10+c-'0';
        return x*f;
    }
    const int maxn=3e5+1;
    const int maxm=1e6+1;
    const int maxp=12;
    struct edge {
        int v,nxt;
    } e[maxm];
    int h[maxn],tot=1;
    bool no[maxm],bridge[maxm];
    void add(int u,int v) {
        e[++tot]=(edge){v,h[u]};
        h[u]=tot;
    }
    int point[maxn][maxp];
    int pc=0,ege[maxn],ec=0,dfn=0,first[maxn],low[maxn];
    int stap[maxn],topp=0;
    struct bian {
        int u,v;
        bian (int u=0,int v=0):u(u),v(v) {}
    } stae[maxm];
    int tope=0;
    bool ins[maxn];
    void Tarjan(int x) {
        first[x]=low[x]=++dfn;
        stap[++topp]=x;
        ins[x]=true;
        for (int i=h[x],v=e[i].v;i;i=e[i].nxt,v=e[i].v) if (!no[i]) {
            no[i]=no[i^1]=true;
            if (!first[v]) {
                stae[++tope]=bian(x,v);
                Tarjan(v);
                low[x]=min(low[x],low[v]);
                if (first[x]<=low[v]) {
                    bian out;
                    ++pc;
                    do {
                        out=stae[tope--];
                        int i;
                        for (i=1;i<=point[out.u][0];++i) if (point[out.u][i]==pc) break;
                        if (i>point[out.u][0]) ++point[out.u][0];
                        point[out.u][i]=pc;
                        for (i=1;i<=point[out.v][0];++i) if (point[out.v][i]==pc) break;
                        if (i>point[out.v][0]) ++point[out.v][0];
                        point[out.v][i]=pc;
                    } while (!(out.u==x && out.v==v));
                }
                if (first[x]<low[v]) {
                    bridge[i]=bridge[i^1]=true;
                }
            } else if (ins[v]) low[x]=min(low[x],first[v]);
        }
        ins[x]=false;
    }
    void dfs(int x) {
        ege[x]=ec;
        for (int i=h[x],v=e[i].v;i;i=e[i].nxt,v=e[i].v) if (!no[i] && !bridge[i]) {
            no[i]=no[i^1]=true;
            dfs(v);
        }
    }
    int main() {
        #ifndef ONLINE_JUDGE
            freopen("test.in","r",stdin);
        #endif
        int n=read(),m=read(),q=read();
        for (int i=1;i<=m;++i) {
            int u=read(),v=read();
            add(u,v),add(v,u);
        }
        for (int i=1;i<=n;++i) if (!first[i]) {
            Tarjan(i);
            if (!point[i][0]) point[i][++point[i][0]]=++pc;
        }
        memset(no,0,sizeof no);
        for (int i=1;i<=n;++i) if (!ege[i]) {
            ++ec,dfs(i);
        }
        while (q--) {
            int op=read(),x=read(),y=read();
            if (op==2) puts(ege[x]==ege[y]?"yes":"no"); else 
            if (op==1) {
                bool flag=false;
                for (int i=1,j=1;i<=point[x][0];++i) {
                    while (j<point[y][0] && point[y][j]<point[x][i]) ++j;
                    if (point[x][i]==point[y][j]) {
                        puts("yes");
                        flag=true;
                        break;
                    }
                }
                if (!flag) puts("no");
            }
        }
        return 0;
    }

    转载于:https://www.cnblogs.com/owenyu/p/6724626.html

    展开全文
  • trajan gabow Kosaraju 双连通分量和强连通分量 希望对大家有助
  • 一、各个概念的定义 1.完全图:  也称简单完全图。假设一个图有n个顶点,那么如果任意两个顶点之间都有边的话,该图就称为完全图。...极大连通子图是无向图的连通分量。(暗指极大连通子图也指无向.

    一、各个概念的定义

    1.完全图
     也称简单完全图。假设一个图有n个顶点,那么如果任意两个顶点之间都有边的话,该图就称为完全图。
    2.连通图(一般都是指无向图):
     从顶点v到w有路径,就称顶点v和m连通。(路径是由顶点和相邻顶点序偶构成的边所形成的序列,其实就是一堆相连的顶点及其边)
     如果图中任意俩顶点都连通,则该图为连通图。
    3.连通分量:
     与连通图对应,一般书上说的都是特指无向图!!
     极大连通子图是无向图的连通分量。(暗指极大连通子图也指无向图!!)
    4.极大连通分量:
     极大是要求该连通子图包含其所有的边(暗指无向图)
    5.极小连通分量:
     极小是在保持连通的情况下使边数最少的子图(暗指无向图)
    6.强连通图(特指有向图):
     在有向图中,若从顶点v到m有路径,则称这俩顶点时强连通的。若任意一对顶点都是强连通的,称此图为强连通图。
     和无向图其实一毛一样,就换个名字以便和无向图区分。
    7.强连通分量:
     有向图中的极大强连通子图称为有向图的强连通分量。
    8.极大强连通分量:
     这里的极大和无向图完全一致
    9.极小强连通分量:
     这里的极小和无向图完全一致
    10.生成树:
     连通图的生成树是包含图中全部顶点的一个极小连通子图
    11.生成森林:
     在非连通图中,连通分量的生成树构成了非连通图的生成森林。

    二、深入理解各个概念

     上面各个概念的基本定义讲完了,看完可能很多人还是一脸懵逼,我当初看那么多概念都懒得去看,更别说去理解了,所以我打算谈谈自己的理解,举例子和画图来帮助大家理解。概念中的序号对应深入的序号,忘记概念网上翻看,可以双开对比看。

    1.完全图:
     对于完全图,他的顶点数是固定的,因此我们如果要研究他的性质,必然要从边上下手。
     对于有向图,考虑一个顶点,如果我们为得到所有不重复的边,那么应该怎么做呢?只考虑从该顶点出去的边或者只考虑射入该顶点的边。如果你不太理解的话,你可以考虑反证法。看下图:
    在这里插入图片描述
    如果上面的证明你看懂了,那么下面的就好做了,如果我们只考虑出去的边,对任一个顶点,与之相关的出边有n-1条总共有n个顶点,所以有向完全图有n*(n-1)条边。
     而对于无向图,任意一条无向图的边应该是有向图对应位置边的一半,所以总边数为n*(n-1)/2.
    2.连通图
    在这里插入图片描述
    3.连通分量:
     首先要知道分量,分量其实就是子图,只不过说的高大尚罢了。但连通分量不是简单的子图连通,他还除了要求子图连通,还要求该连通子图极大。说白了,无向图极大连通子图就是连通分量。到这里先往下看极大连通子图再回来看。
    4.极大连通分量:
     从3我们知道他首先是连通子图,并且该连通子图是极大的,主要是这里的极大很不好理解。这里我画图举例在这里插入图片描述
    5.极小连通分量在这里插入图片描述
    6.强连通图、强连通分量、极大强连通分量、极小连通分量就不用多说了,和无向图一毛一样,只不过他是针对有向图的。
    7.生成树:
     理解了极小连通子图,相信生成树也很容易理解了。
     连通图的生成树是包含图中全部顶点的一个极小连通子图。在这里插入图片描述
    8.生成森林
    在这里插入图片描述

    这就是本文章所有内容了,考研时间宝贵,抽出点时间写博客实属不易,希望对大家能有点帮助,有带佬补充的欢迎评论,有错误欢迎指出~

    展开全文
  • 连通分量:若图G连通,则连通分量便是自身,非连通的无向图有多个连通分量。、 极大连通子图:对于一个连通图,极大连通子图就是其连通分量也就是 其本身,非连通图有多个连通分量则就有多个极大连通子图。主要...

    本文是《刘汝佳算法竞赛》的双连通分量一节的总结

    前置名词讲解

    • 割点: 若无向图G中,存在一个点,当该点被删除时,图G中的连通分量数目增加。整张图不再连通。
    • 连通分量:若图G连通,则连通分量便是自身,非连通的无向图有多个连通分量。、
    • 极大连通子图:对于一个连通图,极大连通子图就是其连通分量也就是 其本身,非连通图有多个连通分量则就有多个极大连通子图。主要理解的是极大,极大指的是这个连通子图不能被其他连通子图所包含。对于一个连通图来说,只有其本身才能不被其他连通子图所包含。
    • 简单环:一个环,除了终点和起点是同一点外,其他点在环中只出现一次。
    • 点双连通:任意两点之间都存在两条“点不重复的路径”。若图G满足,则图称作“点-双连通”的,这个要求等价于任意两条边都在同一简单环中,即内部无割点;
    • 点-双连通分量:一个子图满足点双连通且在图G中是极大(在满足点-双连通的所有子图中是极大的)

    性质

    1. 点双连通分量的任意两条边都存在同一简单环中,有一个例外。
    2. 图中的割点都是至少两个双连通分量的公共点,而非割点则是双连通分量的内部点。
    3. 由上一条性质可知,双连通分量去掉任意一点,仍然保持连通。
    4. 不同双连通分量之间只有一个公共点,当由多个公共点是,则必然被更大的点双连通子图所包含
    5. 一般点双联通图都是简单环,但下面的图仍然可以通过点双连通的测试,大概是两个点都不是割点的原因。

    代码 

    #include<iostream>
    #include<vector>
    #include<algorithm>
    #include<queue>
    #include<string>
    #include<cstring>
    #include<cstdio>
    #include<stack>
    //#include<map>
    #pragma warning(disable:4996)
    using namespace std;
    
    int n, m;
    
    struct Edge
    {
        int u, v;
        Edge(int _u, int _v) :u(_u), v(_v){};
    };
    const int maxn = 300005;
    const int mod = 998244353;
    //从左至右,分别是顶点的dfs标记,割点标记,所属的bcc编号,当前的递归深度,当前的bcc编号
    int pre[maxn], iscut[maxn], bccno[maxn], dfs_clock, bcc_cnt;
    //图G,点双连通图
    vector<int>G[maxn], bcc[maxn];
    //存储遍历的边
    stack<Edge>s;
    
    int dfs(int u, int fa)
    {
    //lowu用于存储与该点直接相连的最远祖先(最小递归深度)
        int lowu = pre[u] = ++dfs_clock;
        int child = 0;
        for (int i = 0; i < G[u].size(); i++)
        {
            int v = G[u][i];
            Edge e = Edge(u, v);
            if (!pre[v])
            {
                s.push(e);
                child++;
                int lowv = dfs(v, u);
                lowu = min(lowu, lowv);
                //若该点的所有子孙节点的最远祖先都比其小,则该点就是割点
                if (lowv >= pre[u])
                {
                    iscut[u] = true;
                    bcc_cnt++;
                    bcc[bcc_cnt].clear();
                    int iswire = 0;
                    while (1)
                    {
                        //以割点为标记,stack中保存的边就是一个点双连通分量。
                        Edge x = s.top(); s.pop();
                        iswire++;
                        if (bccno[x.u] != bcc_cnt)
                        {
                            bcc[bcc_cnt].push_back(x.u);
                            bccno[x.u] = bcc_cnt;
                        }
                        if (bccno[x.v] != bcc_cnt)
                        {
                            bcc[bcc_cnt].push_back(x.v);
                            bccno[x.v] = bcc_cnt;
                        }
                        if (x.u == u&&x.v == v)break;
                    }
                    if (iswire == bcc[bcc_cnt].size())
                       //当点双连通图中的点和边相等时,便是简单环
                }
    
            }
            //当其邻接点是深度较低的点,则比较lowu    
            else if (pre[v] < pre[u] && v != fa)
            {
                s.push(e);
                lowu = min(lowu, pre[v]);
    
            }
        }
        //只有当父节点拥有多个子节点时,才可以是割点。
        if (fa < 0 && child == 1)
            iscut[u] = 0;
        return lowu;
    }
    
    void find_bcc(int n)
    {
        wire = 0;
        memset(pre, 0, sizeof(pre));
        memset(iscut, 0, sizeof(iscut));
        memset(bccno, 0, sizeof(bccno));
        dfs_clock = bcc_cnt = 0;
        for (int i = 1; i <= n; i++)
        {
            if (!pre[i])dfs(i, -1);
        }
    }

     

     

    展开全文
  • 连通分量、双连通分量是无向图相关 强连通分量是有向图相关 关于连通分量 连通分量的定义 无向图中的一个点集,点集中的任意一对点都可以互相到达,且点集外的点与点集中任意一点都不能互相到达。 举个栗例子 这个无...

    连通分量、双连通分量是无向图相关
    强连通分量是有向图相关

    关于连通分量

    连通分量的定义

    无向图中的一个点集,点集中的任意一对点都可以互相到达,且点集外的点与点集中任意一点都不能互相到达。
    举个例子
    在这里插入图片描述这个无向图中存在一个连通分量(显然任意两点均可到达)

    在这里插入图片描述而这个无向图中存在两个连通分量(显然左边三个点可以互相到达,右边三个点可以互相到达,但左边的点无法到达右边的点)

    怎么找连通分量?

    显然,对于一个连通分量,我们可以从它的任何一点开始深搜,每搜到一个点就打一个标记,那么深搜结束的时候必然这个连通分量所有点都被打上了标记。
    所以对于一个无向图,我们只需要枚举每个点,看这个点是否被访问过,若没有则从这个点开始深搜,并给过程中经过的所有点打上访问标记。每个点都被访问过后就说明所有的连通分量都被找到了。由于每个点只会被访问一次,所以时间复杂度是 O ( N ) O(N) O(N)的。

    关于强连通分量

    强连通分量的定义

    有向图中的一个点集,点集中的任意一对点都可以互相到达,且点集外的点与点集中任意一点都不能互相到达。(由于是有向图,A可以到达B但B不能到达A也属于【不能互相到达】的情况)

    怎么找强连通分量?

    tarjan算法
    依然是深搜。
    设立两个辅助数组 d f n [ ] dfn[] dfn[](记录该结点在dfs中是第几个被访问的) l o w [ ] low[] low[]记录该结点能够到达的结点中最小的 d f n [ ] dfn[] dfn[]值。

    • 当第一次访问u时,把 u u u入栈, l o w [ u ] low[u] low[u]= d f n [ u ] dfn[u] dfn[u]
    • 枚举 u u u的每条边(u,v),
    • (1)如果 v v v没有被访问过,访问 v v v,回溯后, l o w [ u ] = m i n ( l o w [ u ] , l o w [ v ] ) low[u]=min(low[u],low[v]) low[u]=min(low[u],low[v]).
    • (2)如果 v v v已经访问过了,说明 v v v u u u的在搜索树中的祖先,此时 l o w [ v ] low[v] low[v]还没有更新,所以low[u]=min(low[u],dfn[v])
    • 如果low[u]==dfn[u],说明当前u的子树是一个强连通分量,无法访问到u以上点,那么进行退栈操作,直到u退出栈。

    双连通分量(待补)

    展开全文
  • 【双连通分量】 一、边双连通分量定义 在分量内的任意两个点总可以找到两条边不相同的路径互相到达。总而言之就是一个圈,正着走反着走都可以相互到达,至少只有一个点。 二、点双连通分量的定义 参照上面,唯一...
  • 识别连通分量

    2017-08-25 16:24:48
    识别图片中的连通分量
  • 连通分量 连通分量:需要保存边用dfs,不需要保存边用并查集 二分图 二分图:非连通图是二分图当且仅当每个连通分量都是二分图。 一个连通图是二分图,当且仅当它可以二染色。 一个连通图是二分图,当且仅当...
  • 该函数返回 ND 逻辑数组(与输入数组大小相同),其中设置了 n 个最大的连通分量索引。 输入: ------- Xin - 输入 ND 阵列。 必需的。 conn - 连通性定义,可以是标量或连通性数组,维数与输入数组相同。 如果为...
  • [BFS][连通分量]求连通分量

    千次阅读 2017-03-23 16:37:58
    求一个图的连通分量 Input n 顶点数() 边(以0 0作为结束标志) Output 连通分量 (强连通图的连通分量为其本身。如果为非连通图,则连通分量为该图的最大连通子图。)分析 建一个100*100的布尔矩阵,b[x,y]=true...
  • 前言 % 被某brz逼着问,觉得很有必要好好复习一下这 些 毒瘤东西。 定义 % 连通 如果有向图中的两点 uuu,vvv 间同时存在 uuu 到 vvv 的路径及 vvv 到 uuu 的路径,则称点 uuu 和点... 连通分量 无向图G的极大...
  • 连通图和连通分量

    万次阅读 多人点赞 2019-08-11 18:41:00
    连通图和连通分量1.顶点间的连通性 在无向图G中,若从顶点vi到顶点vj有路径(当然从vj到vi也一定有路径),快看小说网则称vi和vj是连通的。2.连通图 若V(G)中任意两个不同的顶点vi和vj都连通(即有路径),则称G为...
  • 连通分量定义

    2021-07-18 20:50:12
    百度百科定义:无向图G的极大连通子图称为G的连通分量( Connected Component)。任何连通图的连通分量只有一个,即是其自身,非连通的无向图有多个连通分量。 我の理解:连通分量其实就是一个图里面并查集集合数量...
  • 连通分量

    2021-04-10 18:12:18
    连通分量 什么是强连通图? 如果一个有向图中,存在一条回路,所有的结点至少被经过一次,这样的图为强连通图。 什么是强连通分量? 在强连通图的基础上加入一些点和路径,使得当前的图不再强连通,称原来的强...
  • 连通分量是有向图,双连通分量是无向图。 强连通分量找环时的决策和双连通的决策十分相似,但不完全相同。 强连通分量在if(FF[v])后边的else if还要特判是否在栈里,即vis[v],然后才更新LL[u] 割点和双连通...
  • 连通分量与双连通分量

    千次阅读 2011-09-08 17:51:56
    对于有向连通图,如果任意两点之间都能到达,则称为强连通图。...一个有向图可以有多个强连通分量,一个点也算是强连通分量。强连通分量的术语是strongly connnected components,简称SCC   对于无
  • 连通分量

    2020-08-25 15:49:29
    点双连通分量: 一个图中的点双连通极大子图。点双连通分量是一个“可靠”的图,去掉任意一个点,其他点仍然是连通的。也就是说,点双连通分量中没有割点。 边双连通: 在一个连通图中任意选两点,如果它们之间至少...
  • 深度优先遍历以邻接表表示的图G,输出连通分量的个数和各连通分量的顶点集
  • 作者:Mizuhara链接:强连通分量 - 割点桥 - 双缩点
  • 数据结构与算法--图论之寻找连通分量、强连通分量 寻找无向图的连通分量 使用深度优先搜索可以很简单地找出一幅图的所有连通分量,回忆连通图的概念:如果从任意顶点都存在一条路径达到任意一个顶点,则称这幅图是...
  • 1.Tarjan算法求强连通分量 2. Tarjan算法求割点 3. Tarjan算法求点双连通分量 4. Tarjan算法求割边 5.Tarjan算法求边双连通分量 1.Tarjan算法求强连通分量 了解一下 强连通分量 对于一个有向图的DFS的搜索树...
  • 连通分量

    2013-01-03 19:44:49
    求无向图的连通分量,用的是c++的,喜欢的欢迎下载。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 37,341
精华内容 14,936
关键字:

连通分量