Tarjan算法_缩点

我们这一篇是在已经了解Tarjan算法的基础之上开始写的，如果不了解的话，请先看大牛们关于Tarjan算法的博客。

首先我们先看一下一个问题：一个有向图，有n个点以及m条边，我们至少应该添加几条边才能使整个图变成强连通图。或者是一个无向图至少添加几条边变成连通图。

首先我们对于一个有向无环的图（DAG），至少添加几条边才能使它变为强连通图？我们很容易根据有向无环图的性质得到，我们计算入度为零的点数为a，出度为零的点数为b，那么我们至少需要添加的边数为max(a,b)，如果只有一个点的话，我们不需要添加任何边。

那么我们怎么把一个图转换为DAG呢，因为上面给出的图可能存在环，那么我们就会想到把已经组成全连通的子图转换成一个点来看，那么我们最终的图就不会包含环了。

好了，解决这类问题的思路已经想好了，下面我们来进行求解：

        我们使用Tarjan算法求解出强连通分量之后，我们使用一个belong数组将同一个连通分量的点分配相同的数值，存放在belong数组中，然后我们再次遍历一遍点，然后这次操作的是belong数组中对应的数值，只有把不属于同于个连通分量的边添加到新的图中，并且根据这些边来计算每个缩点的入度以及出度。

//不怕别人比你聪明，就怕别人比你聪明还比你努力
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include <set>
#include <map>
#include<vector>
#define INF 0x3f3f3f3f

using namespace std;
const int MAXN = 1000;
struct Node
{
    int fr;
    int v;
    int next1;
}edge1[MAXN],edge2[MAXN];   //edge1表示还没有缩点之前的图，edge2表示缩点之后的图的连通关系
int head[MAXN];
int dfn[MAXN],low[MAXN];
int vis[MAXN],stact[MAXN];
int belong[MAXN],num[MAXN];
//belong表示每个点属于的缩完之后的哪一个点，num表示每一个缩点里面有多少个点
int cnt,tot,index,now;

void add(int x,int y,Node* edge)
{
    edge[++cnt].next1 = head[x];
    edge[cnt].v = y;
    edge[cnt].fr = x;
    head[x] = cnt;
}

void Tarjan(int x)
{
    low[x] = dfn[x] = ++tot;
    vis[x] = 1;
    stact[++index] = x;

    for(int i = head[x];i != -1; i = edge1[i].next1)
    {
        int v = edge1[i].v;
        if(!dfn[v])
        {
            Tarjan(v);
            low[x] = min(low[x], low[v]);
        }
        else if(vis[v])
            low[x] = min(low[x], dfn[v]);
    }
    if(low[x] == dfn[x])
    {
        ++now;
        do
        {
            printf("%d ",stact[index]);
            vis[stact[index]] = 0;
            belong[stact[index]] = now;
            num[now] ++;
            index --;
        }while(x != stact[index+1]);
        printf("\n");
    }
    return ;
}

int main()
{
    memset(head,-1,sizeof(head));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(vis,0,sizeof(vis));
    memset(stact,0,sizeof(stact));
    memset(belong,0,sizeof(belong));
    memset(num,0,sizeof(num));

    cnt = 0;tot = 0;index = 0;now = 0;
    //now最终表示缩点之后点的数目

    int n,m;
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i = 1;i <= m ;i ++)
    {
        scanf("%d%d",&x,&y);
        add(x,y,edge1);
    }
    for(int i = 1;i <= n;i ++)
        if(!dfn[i])
            Tarjan(i);
    int inde[MAXN];//表示每个缩点的入读
    int outde[MAXN];//每个缩点的出度
    //缩点完成之后，我们就一定没有环的存在
    memset(head,-1,sizeof(head));
    int u,v;
    for(int i = 1;i <= m;i ++)
    {
        u = belong[edge1[i].fr];
        v = belong[edge1[i].v];
        //表示如果这条边不在缩点之内，那么就是用来连接缩点
        if(u!=v)
        {
            add(u,v,edge2);
            inde[v] ++;
            outde[u] ++;
        }
    }
    int a = 0,b = 0;
    //分别计算所的缩点中，入度和出度为0的数目
    for(int i = 1;i <= now;i ++)
    {
        if(!inde[i]) a++;
        if(!outde[i]) b++;
    }
    if(now == 1)
        //如果所有的缩点只有一个，则不需要添加新边
        printf("0\n");
    else
        printf("%d\n",max(a,b));

}
           

6 8
1 3
1 2
2 4
3 4
3 5
4 6
4 1
5 6
           

我们的测试数据如上，答案是需要添加一条边。

我们来看一个例题：Poj 2186

我们要想知道有多说少被全部的认为是受欢迎的，我么先要将他们进行完缩点之后，只有其他的点都可以到达的点才是被其它都欢迎的点。

//不怕别人比你聪明，就怕别人比你聪明还比你努力
//因为和上面程序很类似，所以没有写注释....
include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include <set>
#include <stack>
#include <map>
#include<vector>
#define INF 0x3f3f3f3f

using namespace std;
const int MAXN =  51000;
struct Node
{
    int fr;
    int v;
    int next1;
}edge1[MAXN];
int head[MAXN];
int dfn[MAXN],low[MAXN];
int vis[MAXN],stact[MAXN];
int belong[MAXN],num[MAXN];
int cnt,tot,index,now;
int n,m;

void add(int x,int y,Node* edge)
{
    edge[++cnt].next1 = head[x];
    edge[cnt].v = y;
    edge[cnt].fr = x;
    head[x] = cnt;
}

void Tarjan(int x)
{
    low[x] = dfn[x] = ++tot;
    vis[x] = 1;
    stact[++index] = x;

    for(int i = head[x];i != -1; i = edge1[i].next1)
    {
        int v = edge1[i].v;
        if(!dfn[v])
        {
            Tarjan(v);
            low[x] = min(low[x], low[v]);
        }
        else if(vis[v])
            low[x] = min(low[x], dfn[v]);
    }
    if(low[x] == dfn[x])
    {
        ++now;
        do
        {
            vis[stact[index]] = 0;
            belong[stact[index]] = now;
            num[now] ++;
            index --;
        }while(x != stact[index+1]);
    }
    return ;
}

void Init()
{
    memset(head,-1,sizeof(head));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(vis,0,sizeof(vis));
    memset(stact,0,sizeof(stact));
    memset(belong,0,sizeof(belong));
    memset(num,0,sizeof(num));
    cnt = 0;tot = 0;index = 0;now = 0;
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i = 1;i <= m ;i ++)
    {
        scanf("%d%d",&x,&y);
        add(x,y,edge1);
    }
}
int main()
{
    Init();
    for(int i = 1;i <= n;i ++)
        if(!dfn[i])
            Tarjan(i);
    int u,v;
    int outde[MAXN] = {0};
    for(int i = 1;i <= m;i++)
    {
        u = belong[edge1[i].fr];
        v = belong[edge1[i].v];
        if(u != v)
        {
            outde[u]++;
        }
    }
    int ans = 0;
    for(int i =1;i <= now;i ++)
    {
        if(!outde[i])
        {
            if(ans > 0)
            {
                printf("0\n");
                return 0;
            }
            ans = num[i];
        }
    }
    printf("%d\n",ans);
    return 0;
}