精华内容
下载资源
问答
  • 作者:Mizuhara链接:强连通分量 - 割点桥 - 双缩点

    作者:Mizuhara

    链接:强连通分量 - 割点桥 - 双缩点

    展开全文
  • 强连通分量

    2021-06-21 23:19:38
    了解有向图的强连通分量的求法

    概念

    图 ( G r a p h ) 图 (Graph) (Graph) 是一个二元组 G = ( V ( G ) , E ( G ) ) G=(V(G),E(G)) G=(V(G),E(G))。 其中 V ( G ) V(G) V(G) 是非空集,称为 点 集 ( V e r t e x   s e t ) 点集 (Vertex \ set) (Vertex set),对于 V V V 中的每个元素,我们称其为 顶 点 ( V e r t e x ) 顶点 (Vertex) (Vertex) 节 点 ( N o d e ) 节点 (Node) (Node),简称 点; E ( G ) E(G) E(G) V ( G ) V(G) V(G) 各结点之间边的集合,称为 边 集 ( E d g e   s e t ) 边集 (Edge \ set) (Edge set)
    则有一条边 e i e_i ei 的两个端点分别为 v i − 1 v_{i-1} vi1 v i v_i vi

    无向图

    对于一张无向图 G = ( V , E ) G=(V,E) G=(V,E),对于 u , v ∈ V u,v∈V u,vV,若存在一条途径使得 v 0 = u v_0=u v0=u v k = v v_k=v vk=v,则称 u u u v v v 连 通 的 ( C o n n e c t e d ) 连通的 (Connected) (Connected) 。由定义,任意一个顶点和自身连通,任意一条边的两个端点连通。

    若无向图 G = ( V , E ) G=(V,E) G=(V,E),满足其中任意两个顶点均连通,则称 G G G 连 通 图 ( C o n n e c t e d   g r a p h ) 连通图 (Connected \ graph) (Connected graph) 或 环, G G G 的这一性质称作 连 通 ( C o n n e c t i v i t y ) 连通 (Connectivity) (Connectivity)

    H H H G G G 的一个连通子图,且不存在 F F F 满足 H ⊊ F ⊆ G H⊊F⊆G HFG F F F 为连通图,则 H H H G G G 的一个 连 通 块 / 连 通 分 量 ( C o n n e c t e d   c o m p o n e n t ) 连通块/连通分量 (Connected \ component) /(Connected component)(极大连通子图)。

    有向图

    对于一张有向图 G = ( V , E ) G=(V,E) G=(V,E),对于 u , v ∈ V u,v∈V u,vV,若存在一条途径使得 v 0 = u v_0=u v0=u v k = v v_k=v vk=v,则称 u u u 可达 v v v。由定义,任意一个顶点可达自身,任意一条边的起点可达终点。(无向图中的连通也可以视作双向可达。)

    若有向图 G = ( V , E ) G=(V,E) G=(V,E),满足其中任意两个节点两两互相可达,则称这张图是 强 连 通 的 ( S t r o n g l y   c o n n e c t e d ) 强连通的 (Strongly \ connected) (Strongly connected) 或 环。

    若一张有向图的边替换为无向边后可以得到一张连通图,则称原来这张有向图是 弱 连 通 的 ( W e a k l y   c o n n e c t e d ) 弱连通的 (Weakly \ connected) (Weakly connected)

    与连通分量类似,也有 弱 连 通 分 量 ( W e a k l y   c o n n e c t e d   c o m p o n e n t ) 弱连通分量 (Weakly \ connected \ component) (Weakly connected component)(极大弱连通子图)和 强 连 通 分 量 ( S t r o n g l y   C o n n e c t e d   c o m p o n e n t ) ( 极 大 强 连 通 子 图 ) 强连通分量 (Strongly \ Connected \ component)(极大强连通子图) (Strongly Connected component)

    T a r j a n Tarjan Tarjan 算法

    1. 什么是 T a r j a n Tarjan Tarjan

    T a r j a n Tarjan Tarjan 算法是一种用于求解有向图的强连通分量的算法,时间复杂度为 O ( n + m ) O(n + m) O(n+m)。它可以求出每个强连通分量的大小、属于其的顶点和强连通分量的总数。

    2. 认识 d f s dfs dfs 生成树

    dfs生成树处理强连通分量的一个有力的工具:在 d f s dfs dfs 时,每当通过某条边 e e e 访问到一个新节点 v v v ,就加入这个点和这条边,最后得到的便是 d f s dfs dfs 生成树。例如对于下面这张有向图:
    在这里插入图片描述
    它的 d f s dfs dfs 生成树可能是这样(黑色实线):

    在这里插入图片描述
    有向图的 d f s dfs dfs 生成树主要有 4 4 4 种边(不一定全部出现):

    1. 树 枝 边 ( t r e e   e d g e ) 树枝边(tree \ edge) tree edge:黑色实线,每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。
    2. 前 向 边 ( f o r w a r d   e d g e ) 前向边(forward \ edge) forward edge:灰色虚线,从某个点到它的某个子孙节点(注意不是子节点)的边。
    3. 后 向 边 ( b a c k   e d g e ) 后向边(back \ edge) back edge(也称反祖边):绿色虚线,也被叫做回边,即指向祖先结点的边。
    4. 横 叉 边 ( c r o s s   e d g e ) 横叉边(cross \ edge) cross edge:蓝色虚线,从某个点到一个以被访问过且既非它子孙节点、也非它祖先节点的边。

    定理 1 1 1:反向边和横叉边都有一个特点:起点的 d f s dfs dfs 序必然大于终点的 d f s dfs dfs 序。1

    这可以导出一个有用的结论:对于每个强连通分量,存在一个点是其他所有点的祖先。若不然,则可以把强连通分量划成 n n n 个分支,使各分支的祖先节点互相不为彼此的祖先。这些分支间不能通过树边相连,只能通过至少 n n n 条横叉边相连,但这必然会违背上一段讲的性质。

    在这里插入图片描述
    我们把这个唯一的祖先节点称为强连通分量的根。显然,根是强连通分量中 d f s dfs dfs 序最小的节点。

    定理 2 2 2:如果结点 u u u 是某个强连通分量的根(也就是在在搜索树中遇到的第一个结点),那么这个强连通分量的其余结点肯定是在搜索树中以 u u u 为根的子树中。2

    3. T a r j a n Tarjan Tarjan 的基本思想

    T a r j a n Tarjan Tarjan 算法中,每个结点 u u u 维护了以下几个变量:

    • d f s n [ u ] dfsn[u] dfsn[u]:深度优先搜索遍历时结点 u u u 被搜索的次序(也称为 d f s dfs dfs 序)。

    • l o w [ u ] low[u] low[u]:定义为 u u u 所在子树的节点经过最多一条非树边 u → v u \to v uv (其中 v v v 必须可达 u u u )能到达的节点中最小的 d f s dfs dfs 序。
      根据这样的定义,某个点 p p p 是强连通分量的根,等价于 l o w [ p ] = d f s n [ p ] low[p]=dfsn[p] low[p]=dfsn[p]

      证明:如果 l o w ( p ) = d f s n ( p ) low(p)=dfsn(p) low(p)=dfsn(p) ,说明 p p p 不能到达 d f s dfs dfs 序比 p p p 小的节点,或者说不存在一个强连通分量同时包含 p p p 和某个 d f s dfs dfs 序比 p p p 小的节点。因此, p p p 只能是某个强连通分量的根。

      我们这里必须强调 v v v 可达 u u u ,否则在下图中,会使 l o w [ 5 ] = 2 low[5]=2 low[5]=2 ,但它是一个强连通分量的根。
      在这里插入图片描述

    枚举图中的顶点 v v v,如果 d f s n v = 0 dfsn_{v} = 0 dfsnv=0,说明 v v v 属于一个新的强连通分量,从 v v v 开始搜索。

    接下来,按照深度优先搜索算法搜索的次序对图中所有的结点进行搜索。在搜索过程中,对于以某个点 p p p 为起点的边 p → q p \to q pq

    • 如果 q q q 未访问过,则 q q q p p p 所在的子树上,如果某节点 r r r q q q 起可以经过最多一条后向边到达,则从 p p p 起也可以(先从 p p p q q q ,再到 r r r ),于是先递归处理点 q q q ,然后令 l o w [ p ] = m i n ( l o w [ p ] , l o w [ q ] ) low[p] = min(low[p], low[q]) low[p]=min(low[p],low[q])
    • 如果 q q q 已访问过,且从 q q q 可以到达 p p p ,令 l o w [ p ] = m i n ( l o w [ p ] , d f s n [ q ] ) low[p] = min(low[p],dfsn[q]) low[p]=min(low[p],dfsn[q])
    • 如果 q q q 已访问过,且从 q q q 不能到达 p p p ,不做处理。(后两种情况都是非树边)

    但是我们怎么确认一个点能不能到达另一个点呢?因为反向边和横叉边都指向 d f s dfs dfs 序较小的节点,而前向边的存在又不影响状态转移方程,所以我们只需要确认比该点 d f s dfs dfs 序小的哪些点能到达该点即可,这可以用一个栈动态地维护:

    • 每当搜索到新点,就令它入栈。

    • 如果发现点 p p p 满足 l o w [ p ] = d f s n [ p ] low[p]=dfsn[p] low[p]=dfsn[p] ,则说明 p p p 是某个强连通分量的根,它和栈中的子孙节点相互可达。但同时,它和栈中的子孙节点也无法到达 p p p 的祖先节点,以及祖先节点其他尚未搜索的分支了,所以不断从栈顶弹出元素,直到弹出 p p p (注意这样维护的栈中节点的 d f s dfs dfs 序是单调增的),同时记录答案。

    K o s a r a j u Kosaraju Kosaraju 算法

    K o s a r a j u Kosaraju Kosaraju 简单描述

    K o s a r a j u Kosaraju Kosaraju 算法依靠两次简单的 d f s dfs dfs 实现。

    它有一个重要的特点:求出的强连通分量是按拓扑序排列的。

    第一次 d f s dfs dfs,选取任意顶点作为起点,遍历所有未访问过的顶点,并在回溯之前给顶点编号,也就是后序遍历。

    第二次 d f s dfs dfs,对于反向后的图(反图),以标号最大的顶点作为起点开始 d f s dfs dfs。这样遍历到的顶点集合就是一个强连通分量。对于所有未访问过的结点,选取标号最大的,重复上述过程。

    两次 d f s dfs dfs 结束后,强连通分量就找出来了, K o s a r a j u Kosaraju Kosaraju 算法的时间复杂度为 O ( n + m ) O(n+m) O(n+m)

    算法证明

    练习

    例题

    一道求强连通分量的裸题,要注意判断字典序最小。(然而数据太水)

    可以用以下数据检测自己判断字典序的程序是否正确

    输入

    5 4
    4 3 1
    3 2 1
    4 5 2
    3 1 2
    

    输出

    2
    1 3
    

    A C   c o d e AC \ code AC code

    T a r j a n Tarjan Tarjan

    #include <bits/stdc++.h>
    using namespace std;
    const int maxn = 10005 * 2;
    
    struct node
    {
        int to, nxt;
    } edge[maxn];
    
    int n, m, mx = -1, cnt, cnt_node, cntn, head[maxn], dfn[maxn], low[maxn], siz[maxn], id[maxn];
    bool vis[maxn];
    stack<int> s;
    
    inline void add_edge(int u, int v)
    {
        edge[++cnt].to = v;
        edge[cnt].nxt = head[u];
        head[u] = cnt;
    }
    
    inline void tarjan(int u)
    {
        cnt_node++;
        dfn[u] = low[u] = cnt_node;
        s.push(u);
        vis[u] = 1;
        for (int &e = head[u]; e; e = edge[e].nxt)
        {
            if (!dfn[edge[e].to])
            {
                tarjan(edge[e].to);
                low[u] = min(low[edge[e].to], low[u]);
            }
            else if (vis[edge[e].to])
                low[u] = min(low[u], dfn[edge[e].to]);
        }
        if (low[u] == dfn[u])
        {
            cntn++;
            while (1)
            {
                int now = s.top();
                s.pop();
                vis[now] = 0;
                id[now] = cntn;
                siz[cntn]++;
                if (now == u)
                    break;
            }
        }
    }
    
    int main()
    {
        scanf("%d%d", &n, &m);
        for (int i = 1, u, v, op; i <= m; i++)
        {
            scanf("%d%d%d", &u, &v, &op);
            add_edge(u, v);
            if (op == 2)
                add_edge(v, u);
        }
        for (int i = 1; i <= n; i++)
            if (!dfn[i])
                tarjan(i);
        for (int i = 1; i <= cntn; i++)
            mx = max(mx, siz[i]);
        cout << mx << endl;
        for (int i = 1; i <= n; i++)
            if (siz[id[i]] == mx)
                cout << i << " ";
        return 0;
    }
    

    K o s a r a j u Kosaraju Kosaraju

    #include <bits/stdc++.h>
    using namespace std;
    #define maxn 10005
    #define maxm 100005
    
    struct node
    {
        int to, nxt;
    } edge1[maxm], edge2[maxm];
    
    int n, m, cnt, res1, res2;
    int head1[maxn], head2[maxn];
    int color[maxn], siz[maxn];
    int mx;
    bool vis[maxn];
    stack<int> s;
    
    void add_edge1(int u, int v)
    {
        edge1[++res1].to = v;
        edge1[res1].nxt = head1[u];
        head1[u] = res1;
    }
    
    void add_edge2(int u, int v)
    {
        edge2[++res2].to = v;
        edge2[res2].nxt = head2[u];
        head2[u] = res2;
    }
    
    void dfs1(int u)
    {
        vis[u] = true;
        for (int i = head1[u]; i; i = edge1[i].nxt)
            if (!vis[edge1[i].to])
                dfs1(edge1[i].to);
        s.push(u);
    }
    
    void dfs2(int u)
    {
        color[u] = cnt;
        siz[cnt]++;
        for (int i = head2[u]; i; i = edge2[i].nxt)
            if (!color[edge2[i].to])
                dfs2(edge2[i].to);
    }
    
    void kosaraju()
    {
        for (int i = 1; i <= n; i++)
            if (!vis[i])
                dfs1(i);
        while (!s.empty())
        {
            int v = s.top();
            s.pop();
            if (!color[v])
            {
                cnt++;
                dfs2(v);
            }
        }
    }
    
    int main()
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; i++)
        {
            int u, v, op;
            scanf("%d%d%d", &u, &v, &op);
            add_edge1(u, v);
            add_edge2(v, u);
            if (op == 2)
            {
                add_edge1(v, u);
                add_edge2(u, v);
            }
        }
        kosaraju();
        for (int i = 1; i <= cnt; i++)
        {
            mx = max(mx, siz[i]);
        }
        cout << mx << endl;
        for (int i = 1; i <= n; i++)
            if (siz[color[i]] == mx)
            {
                int now = color[i];
                for (int j = i; j <= n; j++)
                    if (color[j] == now)
                        cout << j << " ";
                break;
            }
        return 0;
    }
    

    T O   B E   C O N T I N U E D \mathcal{TO \ BE \ CONTINUED} TO BE CONTINUED


    1. 证:对于反向边,由于祖先节点的 d f s dfs dfs 序小于子孙节点,所以是显然的。对于横叉边 u → v u→v uv ,由于 v v v 既不是 u u u 的祖先、也不是 u u u 的子孙,所以必然存在一个不同于 u u u v v v 的点 w = l c a ( u , v ) w=lca(u,v) w=lca(u,v) u u u v v v 分别位于两个分支上。 u → v u→v uv 没有成为一条树边,这说明 v v v 所在的分支一定在 u u u 所在的分支之前被访问过,也就是说,分别在 u u u 所在分支和 v v v 所在分支上任取点 p p p q q q ,前者的 d f s dfs dfs 序都一定比后者大,自然也有 d f s n ( u ) > d f s n ( v ) dfsn(u)>dfsn(v) dfsn(u)>dfsn(v) 。得证。 ↩︎

    2. 反证法:假设有个结点 v v v 在该强连通分量中但是不在以 u u u 为根的子树中,那么 u u u v v v 的路径中肯定有一条离开子树的边。但是这样的边只可能是横叉边或者反祖边,然而这两条边都要求指向的结点已经被访问过了,这就和 u u u 是第一个访问的结点矛盾了。得证。 ↩︎

    展开全文
  • 算法讲解:... 例题: poj-2186 ... 题意:总共有n头牛,m个有序对(a, b) 代表牛a崇拜牛b, 崇拜具有传递性,求出被其他所有牛崇拜的牛的总数。 ...题解:构造一个图,进行求强连通分量及缩点,在连通分...

    算法讲解:https://blog.csdn.net/acmmmm/article/details/16361033#comments

    例题:

    poj-2186

    http://poj.org/problem?id=2186

    题意:总共有n头牛,m个有序对(a, b) 代表牛a崇拜牛b, 崇拜具有传递性,求出被其他所有牛崇拜的牛的总数。

    题解:构造一个图,进行求强连通分量及缩点,在强连通分量中的奶牛肯定是被在这个强连通分量里面奶牛所仰慕的,如果一个图里面有几个强连通分量的话那么一定至少存在一个出度为0的点,如果不存在那么刚刚的强连通一定不是最大强连通又想如果有两个这样的出度为0的点存在,那么这个图中一定没有满足题意的奶牛,因为那两个出度为0的点不会仰慕任何牛所以出度为0的点有且只能有一个!如果有多个那么满足题意的牛只有0个,如果没有的话那么整个图都是满足题意的牛。

    ac code:

    #include<iostream>
    #include<cstdio>
    #include<string>
    #include<algorithm>
    #include<queue>
    #include<cstring>
    #include<stack>
    #include<vector>
    using namespace std;
    #define N 10005
    struct eg {
    	int to, next;
    }ac[5*N];
    int n, m, cnt, jar;
    int head[N], dfn[N], low[N], instack[N], belong[N];
    int nu[N];
    vector<int>re[N];
    stack<int>s;
    void init() {
    	memset(nu, 0, sizeof(nu));
    	memset(head, -1, sizeof(head));
    	memset(dfn, 0, sizeof(dfn));
    	memset(instack, 0, sizeof(instack));
    	cnt = 0; jar = 0;
    }
    void add(int u, int v) {
    	ac[cnt].to = v;
    	ac[cnt].next = head[u];
    	head[u] = cnt++;
    }
    void tarjan(int u) {
    	dfn[u] = low[u] = ++cnt;
    	s.push(u);
    	instack[u] = 1;
    	for (int i = head[u]; i != -1; i = ac[i].next) {
    		int v = ac[i].to;
    		if (!dfn[v]) {
    			tarjan(v);
    			low[u] = min(low[u], low[v]);
    		}
    		else if (instack[v])low[u] = min(low[u], dfn[v]);
    	}
    	if (low[u] == dfn[u]) {
    		int now;
    		re[jar].clear();
    		do {
    			now = s.top();
    			s.pop();
    			instack[now] = 0;
    			belong[now] = jar;
    			re[jar].push_back(now);
    		} while (now != u);
    		jar++;
    	}
    }
    int main() {
    	int result = 0;
    	int a, b;
    	scanf("%d%d", &n, &m);
    	init();
    	for (int i = 0; i < m; i++) {
    		scanf("%d%d", &a, &b);
    		add(a, b);
    	}
    	cnt = 0;
    	for (int i = 1; i <= n; i++) {
    		if (dfn[i] == 0)
    			tarjan(i);
    	}
    	for (int i = 1; i <= n; i++) {
    		for (int j = head[i]; j != -1; j = ac[j].next) {
    			int v = ac[j].to;
    			if (belong[i] != belong[v]) {
    				nu[belong[i]] = 1;
    			}
    		}
    	}
    	int ans = 0, t;
    	for (int i = 0; i < jar; i++) {
    		if (!nu[i]) {
    			ans++;
    			t = i;
    		}
    	}
    	if (ans > 1) {
    		cout << result << endl;
    		return 0;
    	}
    	cout << re[t].size() << endl;
    	return 0;
    }

    poj-2553

    http://poj.org/problem?id=2553

    求从u出发能到v,并且从v出发也能到u的这些点,并且将其输出;求出一个图的若干个强连通分量并且如果这个强连通分量中的缩点出度为0的话那么这个强连通分量里面的点就都满足题意。

    ac code:

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<queue>
    #include<stack>
    #include<vector>
    using namespace std;
    #define N 5005
    int n, e, cnt, ans;
    int head[N], dfn[N], low[N], belong[N], nu[N], instack[N], vis[N];
    vector<int>re[N];
    struct eg {
    	int to, next;
    }a[10*N];
    stack<int>s;
    void init() {
    	ans = cnt = 0;
    	memset(head, -1, sizeof(head));
    	memset(nu, 0, sizeof(nu));
    	memset(dfn, 0, sizeof(dfn));
    	memset(instack, 0, sizeof(instack));
    	memset(vis, 0, sizeof(vis));
    }
    void add(int u, int v) {
    	a[cnt].to = v;
    	a[cnt].next = head[u];
    	head[u] = cnt++;
    }
    void tarjan(int u) {
    	dfn[u] = low[u] = ++cnt;
    	s.push(u);
    	instack[u] = 1;
    	for (int i = head[u]; i != -1; i = a[i].next) {
    		int v = a[i].to;
    		if (!dfn[v]) {
    			tarjan(v);
    			low[u] = min(low[u], low[v]);
    		}
    		else if (instack[v])low[u] = min(low[u], dfn[v]);
    	}
    	if (low[u] == dfn[u]) {
    		int now;
    		re[ans].clear();
    		do {
    			now = s.top();
    			s.pop();
    			belong[now] = ans;
    			re[ans].push_back(now); 
    			instack[now] = 0;
    		} while (now != u);
    		ans++;
    	}
    }
    int main() {
    	int x, y;
    	while (~scanf("%d", &n) && n != 0) {
    		scanf("%d", &e);
    		init();
    		for (int i = 0; i < e; i++) {
    			scanf("%d%d", &x, &y);
    			add(x, y);
    		}
    		cnt = 0;
    		for (int i = 1; i <= n; i++) {
    			if (!dfn[i]) {
    				tarjan(i);
    			}
    		}
    		for (int i = 1; i <= n; i++) {
    			for (int j = head[i]; j != -1; j = a[j].next) {
    				int v = a[j].to;
    				if (belong[v] != belong[i]) {
    					nu[belong[i]] = 1;
    				}
    			}
    		}
    		for (int i = 0; i < ans; i++) {
    			if (!nu[i]) {
    				for (int j = 0; j < re[i].size(); j++) {
    					vis[re[i][j]] = 1;
    				}
    			}
    		}
    		int res;
    		for (int i = 1; i <= n; i++) {
    			if (vis[i]) {
    				res = i;
    				cout << i;
    				break;
    			}
    		}
    		for (int i = res + 1; i <= n; i++)
    			if (vis[i])
    				cout << " " << i;
    		cout << endl;
    	}
    	return 0;
    }

    poj-2762

    http://poj.org/problem?id=2762

    题意:一个有向图中有n个点m条边,问是否任意两点u,v之间可以u-v或者v->u。
    思路:学过强连通可以知道,在一个强连通中任意两点都可以满足题目条件。如果图中有多个强连通分量,则需要在强连通分量之间建图,再拓扑排序判断图中是否同时存在一个入度为零的两点,如果存在那么这两点肯定不满足题目条件。

    ac code:

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<queue>
    #include<stack>
    #include<set>
    #include<vector>
    using namespace std;
    #define N 1005
    int n, m, cnt, ans, t;
    int head[N], dfn[N], low[N], belong[N], nu[N], instack[N], vis[N];
    vector<int>re[N];
    struct eg {
    	int to, next;
    }a[10 * N];
    stack<int>s;
    void init() {
    	memset(head, -1, sizeof(head));
    	memset(dfn, 0, sizeof(dfn));
    	memset(instack, 0, sizeof(instack));
    	memset(nu, 0, sizeof(nu));
    	cnt = ans = 0;
    }
    void add(int u, int v) {
    	a[cnt].to = v;
    	a[cnt].next = head[u];
    	head[u] = cnt++;
    }
    void tarjan(int u) {
    	dfn[u] = low[u] = ++cnt;
    	s.push(u);
    	instack[u] = 1;
    	for (int i = head[u]; i != -1; i = a[i].next) {
    		int v = a[i].to;
    		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]) {
    		int now;
    		re[ans].clear();
    		do {
    			now = s.top();
    			s.pop();
    			re[ans].push_back(now);
    			instack[now] = 0;
    			belong[now] = ans;
    		} while (now != u);
    		ans++;
    	}
    }
    void solve() {
    	set<int>st[N];
    	vector<int>h;
    	int flag = 0;
    	for (int i = 1; i <= n; i++) {
    		for (int j = head[i]; j != -1; j = a[j].next) {
    			int v = a[j].to;
    			if (belong[v] != belong[i]) {
    				st[belong[i]].insert(belong[v]);
    			}
    		}
    	}
    	for (int i = 0; i < ans; i++) {
    		for (set<int>::iterator ite = st[i].begin(); ite != st[i].end(); ite++) {
    			//cout << i << " " << *ite << endl;
    			nu[*ite]++;
    		}
    	}                                          
    	for (int i = 0; i < ans; i++) {
    		if (!nu[i]) {
    			h.push_back(i);
    		}
    	}
    	while (1) {
    		if (h.size() == 0)
    			break;
    		if (h.size() > 1) {
    			flag = 1;
    			cout << "No" << endl;
    			break;
    		}
    		int t = h[0];
    		h.clear();
    		for (set<int>::iterator ite = st[t].begin(); ite != st[t].end(); ite++) {
    			nu[*ite]--;
    			//cout << *ite << " " << nu[*ite] << endl;
    			if (nu[*ite] == 0)
    				h.push_back(*ite);
    		}
    	}
    	if (!flag)
    		cout << "Yes" << endl;
    }
    int main() {
    	int u, v;
    	cin >> t;
    	while (t--) {
    		scanf("%d%d", &n, &m);
    		init();
    		for (int i = 0; i < m; i++) {
    			scanf("%d%d", &u, &v);
    			add(u, v);
    		}
    		for (int i = 1; i <= n; i++) {
    			if (!dfn[i]) {
    				cnt = 0;
    				tarjan(i);
    			}
    		}
    		if (ans == 1) {
    			cout << "Yes" << endl;
    		}
    		else {
    			solve();
    		}
    	}
    	return 0;
    }


     

    展开全文
  • 强连通分量】tarjan算法及kosaraju算法+例题阅读前请确保自己知道强连通分量是什么,本文不做赘述。Tarjan算法 一、算法简介  Tarjan算法是一种由Robert Tarjan提出的求有向图强连通分量的时间复杂度为O(n)的...

    【强连通分量】tarjan算法及kosaraju算法+例题

    阅读前请确保自己知道强连通分量是什么,本文不做赘述。

    Tarjan算法
    一、算法简介
      Tarjan算法是一种由Robert Tarjan提出的求有向图强连通分量的时间复杂度为O(n)的算法。

      首先我们要知道两个概念:时间戳(DFN),节点能追溯到的最早的栈中节点的时间戳(LOW)。顾名思义,DFN就是在搜索中某一节点被遍历到的次序号(dfs_num),LOW就是某一节点在栈中能追溯到的最早的父亲节点的搜索次序号。

      Tarjan算法是基于深度优先搜索的算法。在搜索过程中把没有Tarjan过的点入栈,并将该节点的DFN[i]=LOW[i]=++dfs_num(也就是设成他自己),然后以这个节点为树根再进行搜索。当一颗子树搜索完毕时回溯,并在回溯时比较当前节点和目标节点的LOW值,将较小的LOW值赋给当前结点的LOW,这样可以保证每个节点在以其为树根的子树的所有节点中LOW值是最小的。如果回溯时发现当前节点DFN[i]==LOW[i],就将栈中当前结点以上的节点全部弹栈,这些点就组成了一个强连通分量。还要注意一点是,当目标节点进行过Tarjan但还在栈中,就拿当前节点LOW值与目标节点DFN值比较,把更小的赋给当前结点的LOW。

      所以总的来说我们在搜索过程中会遇到以下三种节点:从没访问过的节点(固然不在栈中),访问过但不在栈中的节点,访问过但在栈中的节点。对于三种点我们要分开讨论。

      ①对于从没访问过的节点:加入栈中让其DFN[i]=LOW[i]=++dfs_num,让vis[i]=1表示该点入栈了。这类点的标志是!DFN[i]&&!vis[i]。

      ②对于访问过但不在栈中的节点(!vis[i])直接回溯即可,因为既然该节点访问过了又不在栈中,就必定属于另一个强连通分量。这类点的标志是DFN[i]&&!vis[i]。

      ②对于访问过且在栈中的节点,比较当前节点LOW值和目标节点DFN值,将较小的赋给当前结点LOW值然后回溯。这类点的标志是DFN[i]&&vis[i]。

      在弹栈过程中可以将不同强连通分量染色,方便后续的其他处理(例如缩点,记录不同强连通分量大小等)。

      Tarjan除了用来求强连通分量,还可以用来缩点、求点双连通分量、求LCA等等。

    二、算法模板

    复制代码
     1 void tarjan(int pos){
     2     vis[stack[++index]=pos]=1;//入栈并标记
     3     LOW[pos]=DFN[pos]=++dfs_num;
     4     for(int i=pre[pos];i;i=E[i].next){
     5         if(!DFN[E[i].to]){
     6             tarjan(E[i].to);
     7             LOW[pos]=min(LOW[pos],LOW[E[i].to]);
     8         }
     9         else if(vis[E[i].to]) LOW[pos]=min(LOW[pos],DFN[E[i].to]);
    10     }
    11     if(LOW[pos]==DFN[pos]){
    12         vis[pos]=0;
    13         size[dye[pos]=++CN]++;//染色及记录强连通分量大小
    14         while(pos!=stack[index]){
    15             vis[stack[index]]=0;
    16             size[CN]++;//记录大小
    17             dye[stack[index--]]=CN;//弹栈并染色
    18         }
    19         index--;
    20     }
    21 }

    复制代码
    Kosaraju算法
    一、算法简介
      Kosaraju算法比Tarjan时间复杂度要高,应用范围小,还有着爆栈超内存的风险,但这个算法比Tarjan好理解很多,虽然很玄学。当然和Tarjan一样,Kosaraju也只能用于有向图中。

      Kosaraju也是基于深度优先搜索的算法。这个算法牵扯到两个概念,发现时间st,完成时间et。发现时间是指一个节点第一次被遍历到时的次序号,完成时间是指某一结点最后一次被遍历到的次序号。

      在加边时把有向图正向建造完毕后再反向加边建一张逆图。

      先对正图进行一遍dfs,遇到没访问过的点就让其发现时间等于目前的dfs次序号。在回溯时若发现某一结点的子树全部被遍历完,就让其完成时间等于目前dfs次序号。正图遍历完后将节点按完成时间入栈,保证栈顶是完成时间最大的节点,栈底是完成时间最小的节点。

      (玄学内容开始)然后从栈顶开始向下每一个没有被反向遍历过的节点为起点对逆图进行一遍dfs,将访问到的点记录下来(或染色)并弹栈,每一遍反向dfs遍历到的点就构成一个强连通分量。虽然不知道为什么但他就成强连通分量了…

    二、算法模板
    复制代码

     1 void positive_dfs(int pos){
     2     DFN++;
     3     vis[pos]=1;
     4     for(int i=pre[1][pos];i;i=E[1][i].next)
     5         if(!vis[E[1][i].to])
     6             positive_dfs(E[1][i].to);
     7     stack[N*2+1-(++DFN)]=pos;
     8 }
     9 void negative_dfs(int pos){
    10     dye[pos]=CN;
    11     vis[pos]=0;
    12     size[dye[pos]]++;
    13     for(int i=pre[2][pos];i;i=E[2][i].next)
    14         if(vis[E[2][i].to])
    15             negative_dfs(E[2][i].to);
    16 }
    17 int main(){
    18 
    19         ...... 
    20 
    21     for(int i=1;i<=N;i++)
    22         if(!vis[i])
    23             positive_dfs(i);
    24     for(int i=1;i<=N*2;i++)
    25         if(stack[i]&&vis[stack[i]]){
    26             CN++;
    27             negative_dfs(stack[i]);
    28         }
    29 
    30         ......
    31     
    32 }   

    复制代码
    三、例题/裸题
    codevs1332 上白泽慧音

    时间限制: 1 s
    空间限制: 128000 KB
    题目等级 : 黄金 Gold

    题目描述 Description
    在幻想乡,上白泽慧音是以知识渊博闻名的老师。春雪异变导致人间之里的很多道路都被大雪堵塞,使有的学生不能顺利地到达慧音所在的村庄。因此慧音决定换一个能够聚集最多人数的村庄作为新的教学地点。人间之里由N个村庄(编号为1..N)和M条道路组成,道路分为两种一种为单向通行的,一种为双向通行的,分别用1和2来标记。如果存在由村庄A到达村庄B的通路,那么我们认为可以从村庄A到达村庄B,记为(A,B)。当(A,B)和(B,A)同时满足时,我们认为A,B是绝对连通的,记为

    这里写代码片
    
    
    复制代码
     1 #include <stdio.h>
     2 #include <algorithm>
     3 using namespace std;
     4 int n,m,cnt,index,dfs_num,CN,maxn=-1;
     5 int pre[50010],vis[50010],DFN[50010],LOW[50010],stack[50010],dye[50010],size[50010];
     6 struct pack{int to,next;} E[50010];
     7 void add_edge(int x,int y){
     8     E[++cnt].to=y;
     9     E[cnt].next=pre[x];
    10     pre[x]=cnt;
    11 }
    12 void input(){
    13     scanf("%d%d",&n,&m);
    14     for(int i=1;i<=m;i++){
    15         int a,b,c;
    16         scanf("%d%d%d",&a,&b,&c);
    17         add_edge(a,b);
    18         if(c==2) add_edge(b,a);
    19     }
    20 }
    21 void tarjan(int pos){
    22     vis[stack[++index]=pos]=1;
    23     LOW[pos]=DFN[pos]=++dfs_num;
    24     for(int i=pre[pos];i;i=E[i].next){
    25         if(!DFN[E[i].to]){
    26             tarjan(E[i].to);
    27             LOW[pos]=min(LOW[pos],LOW[E[i].to]);
    28         }
    29         else if(vis[E[i].to]) LOW[pos]=min(LOW[pos],DFN[E[i].to]);
    30     }
    31     if(LOW[pos]==DFN[pos]){
    32         vis[pos]=0;
    33         size[dye[pos]=++CN]++;
    34         while(pos!=stack[index]){
    35             vis[stack[index]]=0;
    36             size[CN]++;
    37             dye[stack[index--]]=CN;
    38         }
    39         index--;
    40     }
    41 }
    42 void output(){
    43     int lenn=0;
    44     int tar;
    45     for(int i=1;i<=n;i++)
    46         if(size[dye[i]]>maxn) maxn=size[dye[i]],tar=i;
    47     printf("%d\n",maxn);
    48     for(int i=1;i<=n;i++)
    49         if(dye[i]==dye[tar]) printf("%d ",i);
    50 }
    51 int main(){
    52     input();
    53     for(int i=1;i<=n;i++)
    54         if(!dye[i]) tarjan(i);
    55     output();
    56     return 0;
    57 } 

    复制代码
    Korasaju:

    复制代码

    
     1 #include <stdio.h>
     2 #include <algorithm>
     3 #include <cstring>
     4 using namespace std;
     5 int N,M,DFN,CN,tot;
     6 int cnt[3],vis[50010],stack[70010],dye[50010],size[50010];
     7 int pre[3][50010];
     8 struct pack{
     9     int to;
    10     int next;
    11 }E[3][50010];
    12 void add_edge(int x,int y,int f){
    13     E[f][++cnt[f]].to=y;
    14     E[f][cnt[f]].next=pre[f][x];
    15     pre[f][x]=cnt[f];
    16 }
    17 void positive_dfs(int pos){
    18     DFN++;
    19     vis[pos]=1;
    20     for(int i=pre[1][pos];i;i=E[1][i].next)
    21         if(!vis[E[1][i].to])
    22             positive_dfs(E[1][i].to);
    23     stack[N*2+1-(++DFN)]=pos;
    24 }
    25 void negative_dfs(int pos){
    26     dye[pos]=CN;
    27     vis[pos]=0;
    28     size[dye[pos]]++;
    29     for(int i=pre[2][pos];i;i=E[2][i].next)
    30         if(vis[E[2][i].to])
    31             negative_dfs(E[2][i].to);
    32 }
    33 int main(){
    34     scanf("%d%d",&N,&M);
    35     for(int i=1;i<=M;i++){
    36         int a,b,t;
    37         scanf("%d%d%d",&a,&b,&t);
    38         add_edge(a,b,1);
    39         add_edge(b,a,2);
    40         if(t==2){
    41             add_edge(b,a,1);
    42             add_edge(a,b,2);
    43         }
    44     }
    45     for(int i=1;i<=N;i++)
    46         if(!vis[i])
    47             positive_dfs(i);
    48     for(int i=1;i<=N*2;i++)
    49         if(stack[i]&&vis[stack[i]]){
    50             CN++;
    51             negative_dfs(stack[i]);
    52         }
    53     int maxn=-1,tar;
    54     for(int i=1;i<=N;i++)
    55         if(size[dye[i]]>maxn) maxn=size[dye[i]],tar=i;
    56     printf("%d\n",maxn);
    57     for(int i=1;i<=N;i++)
    58         if(dye[i]==dye[tar]) printf("%d ",i);
    59     return 0;
    60 }

    复制代码
    bzoj1051 受欢迎的牛

    Time Limit: 10 Sec Memory Limit: 162 MB
    Submit: 3673 Solved: 1940
    Description
    每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛,给你M对整数(A,B),表示牛A认为牛B受欢迎。 这种关系是具有传递性的,如果A认为B受欢迎,B认为C受欢迎,那么牛A也认为牛C受欢迎。你的任务是求出有多少头牛被所有的牛认为是受欢迎的。
    Input
    第一行两个数N,M。 接下来M行,每行两个数A,B,意思是A认为B是受欢迎的(给出的信息有可能重复,即有可能出现多个A,B)
    Output
    一个数,即有多少头牛被所有的牛认为是受欢迎的。
    Sample Input
    3 3
    1 2
    2 1
    2 3
    Sample Output
    1
    HINT
    100%的数据N<=10000,M<=50000

    题解:这道题主要思路是求出强连通分量后将每个强连通分量合并缩成一个节点,然后求出出度为零的节点即可。注意,缩点后只能有一个出度为零的节点,如果有多个答案为0,若没有出度为0的点答案也为0。

    由于这道题我只用了Tarjan写,所以只付上Tarjan AC代码。由于我是用染色处理的,所以Korasaju应该也能写。

    这里写代码片
    
     1 #include <stdio.h>
     2 #include <algorithm>
     3 using namespace std;
     4 int n,m,cnt,re_cnt,top,dfs_num,CN;
     5 int pre[50010],re_pre[50010],tow[50010],DFN[50010],LOW[50010],dye[50010],size[50010],vis[50010];
     6 struct pack{int to,next;} E[50010],re_E[50010];
     7 void add_edge(int x,int y){
     8     E[++cnt].to=y;
     9     E[cnt].next=pre[x];
    10     pre[x]=cnt;
    11 }
    12 void tarjan(int pos){
    13     vis[tow[++top]=pos]=1;
    14     DFN[pos]=LOW[pos]=++dfs_num;
    15     for(int i=pre[pos];i;i=E[i].next){
    16         if(!DFN[E[i].to]){
    17             tarjan(E[i].to);
    18             LOW[pos]=min(LOW[pos],LOW[E[i].to]);
    19         }
    20         else if(vis[E[i].to])
    21             LOW[pos]=min(LOW[pos],DFN[E[i].to]);
    22     }
    23     if(LOW[pos]==DFN[pos]){
    24         vis[pos]=0;
    25         size[dye[pos]=++CN]++;
    26         while(pos!=tow[top]){
    27             vis[tow[top]]=0;
    28             size[dye[tow[top--]]=CN]++;
    29         }
    30         top--;
    31     }
    32 }
    33 void rebuild(){
    34     for(int i=1;i<=n;++i)
    35         for(int j=pre[i];j;j=E[j].next)
    36             if(dye[i]!=dye[E[j].to]){
    37                 re_E[++re_cnt].next=re_pre[dye[i]];//这里写复杂了,其实光统计出度就够了,不用彻底重建图
    38                 re_E[re_cnt].to=dye[E[j].to];
    39                 re_pre[dye[i]]=re_cnt;
    40             }
    41 }
    42 int cal(){
    43     int ret=0;
    44     for(int i=1;i<=CN;++i)
    45         if(!re_pre[i]){
    46             if(ret) return 0;
    47             else ret=size[i];
    48         }
    49     return ret;
    50 }
    51 int main(){
    52     scanf("%d%d",&n,&m);
    53     for(int i=1;i<=m;++i){
    54         int a,b;
    55         scanf("%d%d",&a,&b);
    56         add_edge(a,b);
    57     }
    58     for(int i=1;i<=n;++i)
    59         if(!dye[i]) tarjan(i);
    60     rebuild();
    61     printf("%d",cal());
    62     return 0;
    63 }
    展开全文
  • 强连通分量是有向图,双连通分量是无向图。 强连通分量找环时的决策和双连通的决策十分相似,但不完全相同。 强连通分量在if(FF[v])后边的else if还要特判是否在栈里,即vis[v],然后才更新LL[u] 割点和双连通...
  • tarjan算法的功能很强大, 可以用来求解强连通分量,缩点,桥,割点,LCA等,日后写到相应的模板题我就会放上来。 1.强连通分量(分量中是任意两点间都可以互相到达) 按照深度优先遍历的方式遍历这张图。 遍历...
  • 图论:强连通分量

    2018-08-06 10:14:00
    Luogu2863:利用Tarjan求有...这里的例题题意是这样的,统计所有强连通分量中,至少包含两个点的强连通分量的数量 const int maxn=10005; const int maxm=50005; int n,m,cnt,deep,top,sum,ans; int g[maxn],...
  • 强连通分量-Tarjan

    2017-07-07 19:10:37
    作用Tarjan算法可以将强连通分量合并到该强连通分量的某一个点上,通俗地说就是实现环缩点。有向图的强连通分量有向图中,如果两个点i,j之间既有i->j的路径,又有j->i的路径,则i,j连通。所有点都连通的图是...
  • 强连通分量分解强连通分量分解强连通分量分解 一、强连通分量的定义 有向图强连通分量:在有向图G中,如果两个顶点vi,vj间(vi>vj)有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径,则称两个顶点...
  • 强连通分量: 在非连通图的有向图中,选取部分点为连通图,该连通子图称为强连通分量。 求出强连通分量可以进行缩点操作。 参考:图论——强连通分量(Tarjan算法) 例题:P2746 [USACO5.3]校园网Network of ...
  • 有向图强连通分量

    2020-09-23 00:03:33
    文章目录有向图强连通分量1 基本概念1.1 名词解释1.2 重要性质1.3 结论2. 板子3. 例题3.1 tarjan + 缩点 + 度3.2 tarjan + 缩点 + dp3.2.1 求最长链、求方案数3.2.2 求解差分约束3.2.3 求解必经点问题 有向图强连通...
  • 那有没有时间更优的方法——强连通分量。 分析题意,每个点点权只被计算一次,允许一条边走多次, 那我们考虑用Tarjan来进行缩点, 使图变成有向无环图,再进行DPDPDP。 设转移方程为:f=max(fu+disv,fv)f=max(f_u+...
  • 关于强连通分量

    千次阅读 2017-10-26 11:18:33
    首先要明白什么是强连通分量强连通分量实际上指的是一些点的集合,而这个集合的定义就是:任意集合中的点都能到达其他所有同样在集合中的点 然后就是强连通分量的意义,或者说是作用: 就目前而言,我认为他的...
  • 2.割点集合:在一个无向连通图中,如果有一个顶点集合,删除这个顶点集合,以及这个集合中所有顶点相关联的边以后,原图变成多个连通块,就称这个点集为割点集合。 3.点连通度:最小割点集合中的顶点数。 4.割边(桥...
  • 强连通分量学习记录

    2018-07-16 20:40:03
    近期为了弥补之前知识面窄的尴尬,学了一点图论的内容。强连通分量算是用的很多的一个图论算法。   联通分量的作用在于它...大概关于强连通分量的理解就这么多,具体可以看这篇博客有详细的解释和例题: ht...
  • 初始强连通分量

    2018-04-21 17:16:00
    推荐博客 : https://www.cnblogs.com/wozaixuexi/p/8321602.html... ... 在学习这个算法前,要先知道 : 连通图,连通图,强连通分量 连通图 : 如果两个顶点可以相互到达,则称这两个点连通 连通图 : 如...
  • Tarjan 算法一种由Robert Tarjan提出的求解有向图强连通分量的算法,它能做到线性时间的复杂度。 我们定义: 如果两个顶点可以相互通达,则称两个顶点连通(strongly connected)。如果有向图G的每两个顶点都连通...
  • 强连通分量:有向图的极大连通子图称为强连通分量,注意是极大而非最大,这包含了两个意思:1.有向图的强连通分量可以有多个;2.如果选取了某个子图G2且G2连通,但在图G中还存在一个点v,使得v和G2中任意一个点...
  • 有向图中的极大连通子图称做有向图的强连通分量连通分量:对于图G来的一个子图中,任意两个点都可以彼此到达,这个子图就被称为图G的连通分量(一个点就是最小的连通分量) 最大连通分量:对于图G的一个子图...
  • 强连通分量 在有向图G中,如果任意两个不同的顶点相互可达,则称该有向图是连通的。 Korasaju算法求有向图强连通分量 现在才知道叫这个名字 1.深度优先遍历G,算出每个结点u的结束时间f[u],起 点如何选择...
  • Tarjan算法求强连通分量总结

    千次阅读 2016-07-18 19:12:21
    Tarjan算法求强连通分量总结 首先明确强连通分量的概念:如果图中的任意两个点都能互相到达,则为强连通分量。极大强连通分量:不被其它任何强连通分量包含的强连通分量强连通分量主要与两种边有关:交叉边和后...
  • 对于Tarjan强连通分量算法的理解

    千次阅读 2017-02-22 12:39:17
    对于Tarjan强连通分量算法的理解
  • C++学习笔记:有向图的强连通分量

    千次阅读 2019-05-31 13:55:33
    连通图分量 首先得知道这是个什么玩意儿,对于一个如下的有向图 ...2. 非连通图的极大连通子图,称为强连通分量,孤立的点也是一个强连通分量 (copy课件不解释) 实现方法 1. Kosar...
  • tarjan强连通分量SCC学习笔记变量释义核心流程典型应用 变量释义 tarjantarjantarjan算法的两个核心数组:dfndfndfn数组和lowlowlow数组。 dfn数组:节点在dfsdfsdfs树上的序号(相当于一个时间戳的作用)。 low数组...
  • 【C++】强连通分量

    2020-02-25 09:45:48
    有向图的强连通分量例题 题目链接:http://poj.org/problem?id=2186 vjudge:https://vjudge.net/problem/POJ-2186 题目大意: 有一群牛,总数为N(N<=10000)。 题目数据为牛之间的关系,比如说1仰慕2,2仰慕3...

空空如也

空空如也

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

例题强联通分量