图论-有向图缩点

墨蓝 2022-05-26 01:25 201阅读 0赞

强连通(strongly connected)： 在一个有向图G里，设两个点 a b 发现，由a有一条路可以走到b，由b又有一条路可以走到a，我们就叫这两个顶点（a，b）强连通。

强连通图： 如果 在一个有向图G中，每两个点都强连通，我们就叫这个图，强连通图。

强连通分量strongly connected components)：在一个有向图G中，有一个子图，这个子图每2个点都满足强连通，我们就叫这个子图叫做 强连通分量 。

有向图的缩点就是把有向图中强连通分量缩成一个点（道理很简单，我到了这个强连通分量的任何一点，那么这个强连通分量就能被我访问了），在处理有向图的连通性问题时有很多作用。

比如如下问题:

给出一个 0 ≤ N ≤ 105 点数、0 ≤ M ≤ 105 边数的有向图，

输出一个尽可能小的点集，使得从这些点出发能够到达任意一点，如果有多个这样的集合，输出这些集合升序排序后字典序最小的。

第一行为两个整数 1 ≤ n, m ≤ 105，  
接下来 M 行，每行两个整数 1 ≤ u, v ≤ 105 表示从点 u 至点 v 有一条有向边。

数据保证没有重边、自环。

第一行输出一个整数 z，表示作为答案的点集的大小；

第二行输出 z 个整数，升序排序，表示作为答案的点集。

7 10
    4 5
    5 1
    2 5
    6 5
    7 2
    4 2
    1 2
    5 3
    3 5
    3 6

2
    4 7

不明白缩点的话，是很难做出来的，也有其他方法，这里这是举个例子来解决问题。

缩点其实难在求有向图的强连通分量上面，这个得先去了解一下[点击打开链接][Link 1]

我们把输出的代码改一下，记录到一个数组里面并且同时给每一个点打上标记，即这些点都是一个强连通分量里面的

![70][]num记录的是强连通分量数量，p是记录第几个强连通分量里面的点，unicom表示每一个点属于第几个强连通分量。

算法复杂度O(N+E)

这样我们的预备工作就做好了。把N个点划分成了num个强连通分量块了。

问了验证有向图的联通性，我们还需要利用边的信息。

假如存a->b的边而且unicom\[a\]!=unicom\[b\]即它们俩个点不属于同一强连通分量。那么也就是说我们到达了点a，那么包括点b的强连通分量就全部可以到达了。

我们给强连通分量unicom\[b\]打上标记，这块不用考虑了，考虑a就行了。

![70 1][]S数组保存起点 E数组保存终点  e表示边的条数。

算法复杂度O(E)

总时间复杂度O(E+N)

基本上这个连通性的问题就解决了，对于那些没有打上标记的强连通分量就需要选取到达了。

代码如下:

#include<bits/stdc++.h>
    using namespace std;
    
    const int maxn=1e5+100;
    vector<int> G[maxn],p[maxn],ans;
    int low[maxn],dfn[maxn],Stack[maxn],S[maxn],E[maxn],n,e,cnt,Index,num;
    int link[maxn],unicom[maxn];
    bool vis[maxn];
    
    void tarjan(int u)
    {
        low[u]=dfn[u]=++cnt;
        vis[u]=true;
        Stack[++Index]=u;
        for (int i=0;i<G[u].size();i++) {
            int v=G[u][i];
            if (!dfn[v]) {
                tarjan(v);
                low[u]=min(low[u],low[v]);
            }
            else if (vis[v]){
                low[u]=min(low[u],dfn[v]);
            }
        }
        if (dfn[u]==low[u]) {
           ++num;
           do {
                p[num].push_back(Stack[Index]);
                unicom[Stack[Index]]=num;
                vis[Stack[Index]]=false;
                Index--;
           }while (u!=Stack[Index+1]);
        }
        return ;
    }
    int main()
    {
        scanf("%d%d",&n,&e);
        for (int i=1;i<=e;i++) {
            scanf("%d%d",&S[i],&E[i]);
            G[S[i]].push_back(E[i]);
        }
        memset (vis,false,sizeof(vis));
        for (int i=1;i<=n;i++) {
            if (!dfn[i]) tarjan(i);
        }
        for (int i=1;i<=e;i++) {
            if (unicom[S[i]]!=unicom[E[i]])
                link[unicom[E[i]]]=1;
        }
        for (int i=1;i<=num;i++) sort(p[i].begin(),p[i].end());
        for (int i=1;i<=num;i++) {
            if (!link[i]) ans.push_back(p[i][0]);//选取第一个点就好了
        }
        sort(ans.begin(),ans.end());
        printf("%d\n",ans.size());
        for (int i=0;i<ans.size();i++) {
            printf("%d%c",ans[i],(i==ans.size()-1)?'\n':' ');
        }
        return 0;
    }

[Link 1]: https://blog.csdn.net/wust_cyl/article/details/80036555
[70]: /images/20220526/ddbae4370068478e9705de6e4735fd2b.png
[70 1]: /images/20220526/e42a7fc6c17b4b038cc44741045f90ff.png