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

    2019-08-21 17:16:26
    概念: 强连通:有向图中两个结点如果能两两互相到达,就称这两个点强连通。 强连通图:有向图中所有结点都能...强连通分量是一个环或者一个点。 求强连通分量一般用 Korasaju算法 和 Tarjan算法。 这里我就只记录...

    概念:

    1. 强连通:有向图中两个结点如果能两两互相到达,就称这两个点强连通。
    2. 强连通图:有向图中所有结点都能两两到达,就称强连通图。
    3. 强连通分量:非强连通的有向图的极大强连通子图,称为强连通分量(SCC即Strongly Connected Componenet)。一个图中可以有多个。
    4. 强连通分量是一个环或者一个点。

    求强连通分量一般用 Korasaju算法Tarjan算法
    这里我就只记录tarjan算法。

    这里有一篇大神的文章,我觉得讲的非常好。
    https://www.cnblogs.com/five20/p/7594239.html
    看他里面的tarjan算法的图步骤。

    Tarjan算法:

    简述:
    深搜,如果碰到叶子结点(没有出度的结点),叶子结点就算一个连通分量,如果碰到之前走过的结点v(构成回路了),就回溯,回溯到这个结点v,这段回溯的结点又构成一个强连通分量。

    理解:
    碰到之前搜的结点还不能立刻回溯,因为不能保证这个是极大强连通子图,所以这是要用两个变量dfn[u], low[u], dfn[u] 记录遍历到u结点时的时间(时间戳),low[u]记录碰到之前走过的结点的最小值。所以碰到之前走过的结点的时候就和之前的low比较取最小值,这样就能保证回路回到的是最前面走的结点,这样强连通子图就是最大的。回溯的时候也要更新low[u],保证

    最普遍的写法:
    用栈存深搜中的点,遇到叶结点就出栈,遇到回路也而且回溯到根节点就把根节点以及之前的元素出栈。这里就用到 dfn[u] == low[u] 来判断是否要出栈了。相等表示回溯已经到达根节点,就要弹出元素。弹出的时候记录一下就好了。

    变量:
    数组 dfn[] 和 low[]:表示 遍历到某个结点的时间点 和 深搜树中结点的根节点(可以用来保证是最前面的根)
    stack:栈,存储深搜过程中的结点。
    in_stack[]:标记数组,标记结点是否在栈中。
    idx:时间戳
    一个存强连通分量的数据结构:看具体使用。
    bcnt:强连通分量的数量。
    vis:标记数组,标记结点是否已访问,这个可有可无,因为代码中可以中dfn来替代,dfn中0代表未访问,大于零表示访问过。

    步骤:
    深搜,
    时间戳加一,
    设置dfn[u]和low[u]的初始值为时间戳的值,dfn[u] = low[u] = idx,
    u点入栈,标记u点入站
    遍历u点的子结点:
    如果没访问过就继续递归深搜,深搜完回溯时,要更新low[u]
    访问过而且在栈中,表示遇到回路了,就更新low[u]
    访问完子结点就判断是否要出栈。 dfn[u] == low[u] 就出栈。
    强连通分量的数量加一,用一个数据结构存储当前的分量。这里我用了python的字典{k: id , v: 列表}。

    伪代码:伪代码出自这本书中《Competitive Programming 3》

    vi dfs_num, dfs_low, S, visited; // global variables
    
    void tarjanSCC(int u) {
    	dfs_low[u] = dfs_num[u] = dfsNumberCounter++; // dfs_low[u] <= dfs_num[u]
    	S.push_back(u); // stores u in a vector based on order of visitation
    	visited[u] = 1;
    	for (int j = 0; j < (int)AdjList[u].size(); j++) {
    		ii v = AdjList[u][j];
    		if (dfs_num[v.first] == UNVISITED)
    			tarjanSCC(v.first);
    		if (visited[v.first] && v.first in S) // condition for update
    			dfs_low[u] = min(dfs_low[u], dfs_low[v.first]); }
    
    	if (dfs_low[u] == dfs_num[u]) { // if this is a root (start) of an SCC
    		printf("SCC %d:", ++numSCC); // this part is done after recursion
    		while (1) {
    			int v = S.back(); S.pop_back(); visited[v] = 0;
    			printf(" %d", v);
    			if (u == v) break; }
    		printf("\n");
    } }
    
    // inside int main()
    	dfs_num.assign(V, UNVISITED); dfs_low.assign(V, 0); visited.assign(V, 0);
    	dfsNumberCounter = numSCC = 0;
    	for (int i = 0; i < V; i++)
    	if (dfs_num[i] == UNVISITED)
    		tarjanSCC(i);
    

    c++模板参照上面推荐的博客。
    Tarjan python模板:

    def tarjan(u):
        global idx
        global bcnt
        idx += 1
        dfn[u] = low[u] = idx
        stack.append(u)
        in_stack[u] = True
    
        for v in graph[u]:
            if not dfn[v]:
                tarjan(v)  # dfs(v)
                low[u] = min(low[u], low[v])  # 回溯
            elif in_stack[v]:
                low[u] = min(low[u], dfn[v])
    
        # 回溯后,判断dfn[u] == low[u],把u以上的点弹出
        if dfn[u] == low[u]:
            sccs[bcnt] = []
            while True:
                v = stack.pop()
                in_stack[v] = False
                sccs[bcnt].append(v)
                if u == v:
                    break
            bcnt += 1
    

    完整代码如下:
    数据参考图来自上面推荐博客。
    在这里插入图片描述

    python代码:

    import sys
    
    sys.setrecursionlimit(10 ** 7)
    
    
    def tarjan(u):
        global idx
        global bcnt
        idx += 1
        dfn[u] = low[u] = idx
        stack.append(u)
        in_stack[u] = True
    
        for v in graph[u]:
            if not dfn[v]:
                tarjan(v)  # dfs(v)
                low[u] = min(low[u], low[v])  # 回溯
            elif in_stack[v]:
                low[u] = min(low[u], dfn[v])
    
        # 回溯后,判断dfn[u] == low[u],把u以上的点弹出
        if dfn[u] == low[u]:
            sccs[bcnt] = []
            while True:
                v = stack.pop()
                in_stack[v] = False
                sccs[bcnt].append(v)
                if u == v:
                    break
            bcnt += 1
    
    
    # 数据
    edges = [
        [0, 1],
        [1, 2],
        [2, 3],
        [2, 4],
        [3, 4],
        [3, 1],
        [0, 5],
        [5, 6],
        [6, 0],
    ]
    
    n = 7
    
    # 构图
    graph = [[] for _ in range(n)]
    for a, b in edges:
        graph[a].append(b)
    
    # dfn: 结点的时间戳,顺便充当标记数组,0代表未被访问,大于0表示访问过
    # low: dfs树的根,强连通分量的根
    dfn, low = [0] * n, [0] * n
    
    stack = []
    
    # 标记是否在栈中
    in_stack = [False] * n
    
    # 当前时间,时间戳
    idx = 0
    
    # 图中包含的所有的强连通分量
    sccs = {}
    
    # 强连通分量的数量
    bcnt = 0
    
    # 找强连通分量
    tarjan(0)
    
    for k, v in sccs.items():
        print(k, [chr(e + ord('a')) for e in sorted(v)])
    
    
    展开全文
  • 强连通分量是有向图相关 关于连通分量 连通分量的定义 无向图中的一个点集,点集中的任意一对点都可以互相到达,且点集外的点与点集中任意一点都不能互相到达。 举个栗例子 这个无向图中存在一个连通分量(显然任意...

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

    关于连通分量

    连通分量的定义

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

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

    怎么找连通分量?

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

    关于强连通分量

    强连通分量的定义

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

    怎么找强连通分量?

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

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

    双连通分量(待补)

    展开全文
  • 强连通分量是有向图,双连通分量是无向图。 强连通分量找环时的决策和双连通的决策十分相似,但不完全相同。 强连通分量在if(FF[v])后边的else if还要特判是否在栈里,即vis[v],然后才更新LL[u] 割点和双连通...

    概要:

    各种dfs时间戳。。全是tarjan(或加上他的小伙伴)无限膜拜tarjan orzzzzzzzzz

    技巧及注意:

    强连通分量是有向图,双连通分量是无向图。

    强连通分量找环时的决策和双连通的决策十分相似,但不完全相同。

    强连通分量在if(FF[v])后边的else if还要特判是否在栈里,即vis[v],然后才更新LL[u]

    割点和双连通分量因为是无向图所以要判个fa,可以在dfs时维护个fa参数

    割点如果要求分割的分量,那么就是这个节点对他的子树是割点的数目+1。

    割点不需要栈维护但是要在后边判当前节点是否为root(即child==1且为root时,这个点就不是割点),而双连通分量不需要特判根节点,而需要在LL[v]>=FF[u]那里直接维护bcc即可。

    割边的话其实就是割边的特例即可,即LL[u]>FF[u]就行了。。千万不要写错。。

    边-双连通分量的话比点的好做,就是求出割边后所有不经过割边的环就都是了,dfs之。

    点-双连通分量似乎也是存边然后取边集中的点?等做完bzoj cactus先吧。。。

    缩点后一定要注意重边啊!!!

    1. 【BZOJ】1093: [ZJOI2007]最大半连通子图(tarjan+拓扑序)

    割点例题:

    1. 【POJ】1523 SPF(割点)(注意特判root)

    割边例题:

    1. 【vijos】1769 网络的关键边(割边)(注意割边不要写错)

    双连通分量例题:

    1. 【POJ】2942 Knights of the Round Table(双连通分量)(注意不要忘记栈是在两个if内添加的)

    将有环图转换成dag然后解决问题,例题:

    1. 【BZOJ】1093: [ZJOI2007]最大半连通子图(tarjan+拓扑序)

     

    转载于:https://www.cnblogs.com/iwtwiioi/p/4003405.html

    展开全文
  • Tarjan 强连通分量

    2019-03-13 19:58:40
    构成强连通分量是必定是dfs树的一棵子树,在对树进行dfs的时候记录访问时间dfn和以该节点为根节点的子树的最小编号low,将节点加入栈中并递归它的子节点,子节点在栈中更新根节点的low,子节点没有访问过就继续递归...

    强连通分量

    • 图中找到一个最大的子图,使得子图中任意两个节点相互到达。
    • 一个点也是一个强连通分量

    Tarjan

    构成强连通分量是必定是dfs树的一棵子树,在对树进行dfs的时候记录访问时间dfn和以该节点为根节点的子树的最小编号low,将节点加入栈中并递归它的子节点,子节点在栈中更新根节点的low,子节点没有访问过就继续递归下去。
    在回溯的时候,当dfn == low 表示该点可以通过栈中的节点回到原点,也就形成一个强连通分量

    int dfn[maxn], low[maxn], Stack[maxn], inStack[maxn], belong[maxn], in[maxn], ts, cnt, len;
    void init(int n) {
    	for (int i = 1; i <= n; ++i) g[i].clear();
    	ts = cnt = len = 0;
    	fill(dfn, dfn+n+1, 0);
    	fill(inStack, inStack+n+1, 0);
    }
    void tarjan(int u) {
    	dfn[u] = low[u] = ++ts;
    	inStack[u] = 1;
    	Stack[len++] = u;
    	for (int i = 0; i < (int)g[u].size(); ++i) {
    		int v = g[u][i];
    		if (!dfn[v]) {
    			tarjan(v);
    			low[u] = min(low[u], low[v]);
    		}else if (inStack[v]) low[u] = min(low[u], dfn[v]);
    	}
    	if (dfn[u] == low[u]) {
    		cnt++;
    		while (1) {
    			int top = Stack[--len];
    			belong[top] = cnt;
    			inStack[top] = 0;
    			if (top == u) break;
    		}
    	}
    }
    for (int i = 1; i <= n; ++i) {
    	if (dfn[i]) continue;
    	tarjan(i);
    }
    
    展开全文
  • 强连通分量板子

    2017-11-08 19:58:59
    【这道题没有过poj2186,不过二分...因为强连通分量是针对有向图,所以没有什么if(v==fa) continue;的说法 2.else后面一定还要判断if(instk[v]) 非常重要!!这点和双连通分量不同!!#include #include #include<a
  • 今天学习了强连通分量的Kosaraju算法,网上写的人也不多,但是...强连通分量是针对有向图定义的,为了区别无向图的联通分量的概念。在一个强连通分量中,任意两点都相互可达。 这个图中就存在三个强连通分量,分...
  • 强连通分量与双连通分量

    千次阅读 2011-09-08 17:51:56
    对于有向连通图,如果任意两点之间都能到达,则称为强连通图。...一个有向图可以有多个强连通分量,一个点也算是强连通分量强连通分量的术语是strongly connnected components,简称SCC   对于无
  • 今天是算法数据结构专题的第35篇文章,我们来聊聊图论当中的强连通分量分解的Tarjan算法。Kosaraju算法一看这个名字很奇怪就可以猜到它也是一个根据人名起的算法,它的发明人是S. Rao Kosaraju,这是一个在图论当中...
  • 强连通分量总结

    千次阅读 2014-08-02 22:31:23
    这个算法主要依赖的是图G与图G的转置强连通分量是一样的。 具体证明先不考虑了(既是强连通分量,正向可以到达,反向一定也可以到达)。 实现过程 1. dfs原图G,并且记录结束时间(后序)。后序越大,为相对的根...
  • 强连通分量是啥呢? 在有向图G中,如果两个顶点vi,vj间(vi>vj)有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径,则称两个顶点强连通。如果有向图G的每两个顶点都强连通,称G是一个强连通图。有向...
  • 强连通分量 Tarjan

    2019-12-03 13:39:22
    强连通分量 Tarjan 前言 其实很早就会用Tarjan打强连通了,但还是有些一知半解,也忘性大,现在总结一下。 强连通分量的定义 假设我们现在有这个图: 很显然这三个点两两之间可以到达,那么我们就称这个图是强连通...
  • 强连通分量 简介 在阅读下列内容之前,请务必了解图论基础部分。 强连通的定义是:有向图 G 强连通是指,G 中任意两个结点连通。 强连通分量(Strongly Connected Components,SCC)的定义是:极大的强连通子图...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,514
精华内容 1,405
关键字:

强连通分量是