图论——有向图的连通性问题

  • Post author:
  • Post category:其他




前言:

一些概念需要我们理解一下,以便更好地进行下面的内容。

  • 在有向图G中,如果两个顶点间至少存在一条互相可达路径,称两个顶点强连通(strongly connected)。
  • 如果有向图G的每两个顶点都强连通,称G是一个强连通图。
  • 非强连通图有向图的极大强连通子图,称为强连通分量(strongly connected components)。


很明显强连通分量出现在有向有环图中,每一个连通的分量都可以被当作是强连通分量。如左下图每一个虚线框内都是一个强连通分量(SCC),右下图则将强连通分量当作一个结点后构成的一个DAG

在这里插入图片描述



解决方法:Tarjan算法

Tarjan算法基于

深度优先搜索树

,其有两个重要变量dfn[u]:表示在深度搜索中遍历到该节点的次序(设置一个时间戳变量即可)。low(u)表示以u节点为树根,u及u以下树节点所能找到的最小次序号。


注意Tarjan认为单个节点自身就是一个强联通分量

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;    //先给遍历的点设置上时间戳
    stk[ ++ top] = u, in_stk[u] = true;   //入栈

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);    //这里表示已经遍历完u的某一个后继节点,需要更新low[u],low的定义参照上面所述
        }
        else if (in_stk[j])  //看是否在栈里,如果在,证明该点所连接的点没有分到哪个SCC上,所以就可以继续更新low[u]
            low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u])  //这里是某个SCC上的第一个入栈的点一定是整个SCC都能达到的最小时间戳,可以简单地认为这个就是老大,虽然SCC是个环
    {
        ++ scc_cnt;
        int y;
        do {
            y = stk[top -- ];
            in_stk[y] = false;
            id[y] = scc_cnt;   //表示该点是哪个SCC
        } while (y != u);                //这里还可以统计SCC内部的节点个数
    }
}


这里有一篇博客,讲low数组的含义还不错,请点击!






这里我们用例题来深入了解这个算法



例题一:

在这里插入图片描述

在这里插入图片描述

思路:

TarjanTarjan 缩点将原图转化成 DAG,统计每个强连通分量的出度入度,起点数量为 srcsrc,终点数量为 desdes。对于一个强连通分量,其中只要有一所学校获得新软件那么整个分量都能获得。

很明显只要统计一下入度为0 的SCC个数,即就是第一问的答案

第二问,其实就是求添加多少条边能使

缩点

后的DAG图变成一个强连通图,而这个做法也是有向图的强连通分量的后续操作,也就是把每个SCC求出来后,你会发现把这些”缩点”后(常做的方法就是统计出入度即可,不需要真正的缩点,但有时是要建立图的),就形成了DAG图,很明显就可以转换成拓扑排序,而且这还有个性质,

如果我们按照SCC的编号从大到小遍历,那么我们就是按照拓扑排序进行遍历的。


这里有个规律,统计入度为0的个数和出度为0的个数,那么添加的边的条数就是cnt = max(p,q);

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110, M = 10010;

int n;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt;
int din[N], dout[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;    //先给遍历的点设置上时间戳
    stk[ ++ top] = u, in_stk[u] = true;   //入栈

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);    //这里表示已经遍历完u的某一个后继节点,需要更新low[u],low的定义参照上面所述
        }
        else if (in_stk[j])  //看是否在栈里,如果在,证明该点所连接的点没有分到哪个SCC上,所以就可以继续更新low[u]
            low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u])  //这里是某个SCC上的第一个入栈的点一定是整个SCC都能达到的最小时间戳,可以简单地认为这个就是老大,虽然SCC是个环
    {
        ++ scc_cnt;
        int y;
        do {
            y = stk[top -- ];
            in_stk[y] = false;
            id[y] = scc_cnt;   //表示该点是哪个SCC
        } while (y != u);                //这里还可以统计SCC内部的节点个数
    }
}

int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ )
    {
        int t;
        while (cin >> t, t) add(i, t);
    }

    for (int i = 1; i <= n; i ++ )
        if (!dfn[i])
            tarjan(i);

    for (int i = 1; i <= n; i ++ )        //这个就是缩点,并未真正的建图
        for (int j = h[i]; j != -1; j = ne[j])
        {
            int k = e[j];
            int a = id[i], b = id[k];
            if (a != b)
            {
                dout[a] ++ ;
                din[b] ++ ;
            }
        }

    int a = 0, b = 0;
    for (int i = 1; i <= scc_cnt; i ++ )
    {
        if (!din[i]) a ++ ;
        if (!dout[i]) b ++ ;
    }

    printf("%d\n", a);
    if (scc_cnt == 1) puts("0");
    else printf("%d\n", max(a, b));

    return 0;
}


例题二:

在这里插入图片描述

在这里插入图片描述

思路:这里就是先求SCC,保存每个SCC的内部节点个数,然后进行缩点加判断,如果出现两个以上出度为0的SCC,那么就无解。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010, M = 50010;

int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt, Size[N];
int dout[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[ ++ top] = u, in_stk[u] = true;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u])
    {
        ++ scc_cnt;
        int y;
        do {
            y = stk[top -- ];
            in_stk[y] = false;
            id[y] = scc_cnt;
            Size[scc_cnt] ++ ;
        } while (y != u);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }

    for (int i = 1; i <= n; i ++ )
        if (!dfn[i])
            tarjan(i);

    for (int i = 1; i <= n; i ++ )
        for (int j = h[i]; ~j; j = ne[j])
        {
            int k = e[j];
            int a = id[i], b = id[k];
            if (a != b) dout[a] ++ ;
        }

    int zeros = 0, sum = 0;
    for (int i = 1; i <= scc_cnt; i ++ )
        if (!dout[i])
        {
            zeros ++ ;
            sum += Size[i];
            if (zeros > 1)
            {
                sum = 0;
                break;
            }
        }

    printf("%d\n", sum);

    return 0;
}



例题三:

在这里插入图片描述

在这里插入图片描述

思路:

  • 这道题是有点难度的,首先我们得建立这样一个关系

    如图:

    在这里插入图片描述

    这就把题目中的五种关系转换成图的边的关系,从而用图的相关知识点进行解答。


  • 建图之前我们先设置一个超级源点0将各个点相连接起来,边长依旧设置为1,而dist[0] ==0,这样就能保证与超级源点相连接的点的dist[x]=1(也就是能保证后面形成的每个环,这里指的是无前驱的环,最起码环的dist[x]至少为1,保证初始化值的正确性)

  • 这时就用tarjan算法求scc强连通分量,还要统计一下每个scc环的内部节点数量

  • 缩点建立新图,建图的过程中根据题意进行判断,如果其中scc存在边长大于0的正环,那么这题就是无解的,只有这么一种情况才是允许的,环中的边长为0,即每个点的dist[x]是一样的。

  • 在有解的情况下,对scc编号从大到小进行遍历(这时候一定是拓扑序列),然后逐个进行dist[]数组的更新,也就是求按照拓扑序列求每个点到超级源点的最大值(

    我们不需要求出拓扑序列,因为只要按照scc的编号从大到小进行遍历,那么这就一定是拓扑序列,还有这里是最大值,而不是最小值,切记,切记!!!

    )如图:

    在这里插入图片描述



代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010, M = 600010;

int n, m;
int h[N], hs[N], e[M], ne[M], w[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt, Size[N];
int dist[N];
int in_du[N]={0};

void add(int h[], int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    in_du[b]++;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[ ++ top] = u, in_stk[u] = true;

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u])
    {
        ++ scc_cnt;
        int y;
        do {
            y = stk[top -- ];
            in_stk[y] = false;
            id[y] = scc_cnt;
            Size[scc_cnt] ++ ;
        } while (y != u);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    memset(hs, -1, sizeof hs);

   for(int i=1;i<=n;++i) add(h,0,i,1);

    while (m -- )
    {
        int t, a, b;
        scanf("%d%d%d", &t, &a, &b);
        if (t == 1) add(h, b, a, 0), add(h, a, b, 0);
        else if (t == 2) add(h, a, b, 1);
        else if (t == 3) add(h, b, a, 0);
        else if (t == 4) add(h, b, a, 1);
        else add(h, a, b, 0);
    }
    
    //for(int i=1;i<=n;++i) add(h,0,i,1);
    
    

    tarjan(0);

    bool success = true;
    //idx  = 0;
    for (int i = 0; i <= n; i ++ )
    {
        for (int j = h[i]; ~j; j = ne[j])
        {
            int k = e[j];
            int a = id[i], b = id[k];
            if (a == b)
            {
                if (w[j] > 0)
                {
                    success = false;
                    break;
                }
            }
            else add(hs, a, b, w[j]);
        }
        if (!success) break;
    }

    if (!success) puts("-1");
    else
    {
        for (int i = scc_cnt; i; i -- )
        {
            for (int j = hs[i]; ~j; j = ne[j])
            {
                int k = e[j];
                dist[k] = max(dist[k], dist[i] + w[j]);
            }
        }

        LL res = 0;
        for (int i = 1; i <= scc_cnt; i ++ ) res += (LL)dist[i] * Size[i];

        printf("%lld\n", res);
    }

    return 0;
}



版权声明:本文为weixin_43743711原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。