tarjan缩点学习笔记

【模板】tarjan缩点学习笔记

tarjan缩点详解

P2341 [HAOI2006]受欢迎的牛

#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;
const int N=1e4+5,M=5e4+1;
int n,m,tot,idx,sum;
stack<int>s;
int head[N],color[N],dfn[N],dnum[N],start[N],low[N];
bool mark[N];
struct edge{
    int s,e,next;
}ed[M];
void tarjan(int x)
{
    low[x]=dfn[x]=++idx;
    s.push(x);
    mark[x]=1;
    for (int i=head[x];i;i=ed[i].next)
    if (!dfn[ed[i].e])
    {
        tarjan(ed[i].e);
        low[x]=min(low[ed[i].e],low[x]);
    }
    else if (mark[ed[i].e])
    low[x]=min(low[x],dfn[ed[i].e]);
    if (low[x]==dfn[x])
    {
        ++sum;
        int k;
        do
        {
            k=s.top();
            s.pop();
            mark[k]=0;
            color[k]=sum;
            dnum[sum]++;
        }while (k!=x);
    }
    return ;
}
inline void add(int s,int e)
{
    ed[++tot]=(edge){s,e,head[s]};
    head[s]=tot;
    return ;
}
int main()
{
    scanf("%d%d",&n,&m);
    int s,e;
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d",&s,&e);
        add(s,e);
    }
    for (int i=1;i<=n;i++)
    if (!dfn[i]) tarjan(i);
    for (int i=1;i<=tot;i++)
    if (color[ed[i].s]!=color[ed[i].e])
    start[color[ed[i].s]]++;
    int num=0,ans;
    for (int i=1;i<=sum;i++)
    {
        if (!start[i])
        {
            num++;
            ans=i;
        }
        if (num>=2)
        {
            printf("0\n");
            return 0;
        }
    }
    printf("%d",dnum[ans]);
    return 0;
}

用dfs遍历一个图的所有点，会先搜出来一棵树，然后判断是否有返祖边，有返祖边即有强联通分量。

如图

1. 红色代表第一次找到第一个返祖边的过程
2. 粉红色代表回溯并更新low数组的过程
3. 蓝色代表再次找另一个返祖边的过程（因为这个强联通分量没有找完，所以不会缩点）
4. 绿色代表再次回溯更新low数组的过程
5. 棕色代表再次寻找返祖边
6. 没有找到，对棕色部分进行缩点
7. 然后一直回溯到low=dfn=1，对紫色部分进行缩点

    if (!dfn[ed[i].e])
    {
        tarjan(ed[i].e);
        low[x]=min(low[ed[i].e],low[x]);
    }

寻找操作和回溯更新操作

    else if (mark[ed[i].e])
    low[x]=min(low[x],dfn[ed[i].e]);

找的返祖边更新low的操作

    if (low[x]==dfn[x])
    {
        ++sum;
        int k;
        do
        {
            k=s.top();
            s.pop();
            mark[k]=0;
            color[k]=sum;
            dnum[sum]++;
        }while (k!=x);
    }

缩点操作，把到这个点以前栈里所有点染同一种颜色，表示在同一个强联通分量里

    if (mark[ed[i].e])

为什么要用mark[]数组单独标记在不在栈里面呢？？
例子：如图当一个正在缩点的点指向一个已经缩完的点集时，如果没有mark[]数组单独标记，就会把low[]的值更新为一个在return ;时永远也到不了的值，完成不了这个点所在点集的缩点。

tarjan缩点学习笔记

原文：https://www.cnblogs.com/last-diary/p/10609810.html