tarjan复习笔记

2024-02-28 12:23:16

tarjan复习笔记

（关于tarjan读法，优雅一点读塔洋，接地气一点读塔尖）

0. 连通分量

有向图：

强连通分量（SCC）是个啥

就是一张图里面两个点能互相达到，那么这两个点在同一个强连通分量里，
极大强连通分量就是最大的强连通分量。

无向图：

一个全部联通的子图就是一个连通分量。
其中用到tarjan暂时还有边双连通分量（e-DCC）和点双连通分量（v-DCC）

边双连通分量（e-DCC）

指的是一个子图中没有桥的话，这就是一个边双连通分量。
一个无向图的每一个极大边双连通子图称作此无向图的双连通分量。

点双连通分量（v-DCC）

对于一个无向图，如果一个点集，它内部的任意一个点对之间，至少有两条点完全不重复的路径，那么这个点集就是原图的一个点双连通分量。

无向图的双连通分量下面待会复习

tarjan求强连通分量

这个就是所谓的tarjan强连通分量——缩点了。

对于一个单向联通的子图，我们从一个点出发会得到一个搜索树，
但是这个子图可不仅仅只有搜索树上的边。

（搜索树上的边下简称树边，非搜索树上的但是遇到的边下简称非树边）

按照搜索的顺序把点压到一个栈里。
如果当前我们找到一个非树边然后指向之前栈中的点里，那么从那个点到这个点之间都是强连通分量的一部分。

但是我们怎么找到一个最大的强连通分量呢？

我们设置一个搜索顺序dfn[]和追溯值low[]，让当前点的low[]取到能够到的最靠上的点的dfn[]或者自己的dfn[]。
如果这个dfn[]!=low[]，那么就是栈从当前点到下面的这些点都是在一个强连通分量里面。

可以证明这样求的一定是一个个最大的强连通分量。

代码实现（【模板】）：

#include <iostream>
#include <cstdio>

using namespace std;
const int maxn=10086;
//forward star node
struct edge
{
    int to,next;
} Edge[50086];
int cnt=1,head[maxn];
//forward star add edges
inline void add_edge(int from,int to)
{
    Edge[cnt]=(edge){to,head[from]};
    head[from]=cnt++;
}
//tarjan uses
int dfn[maxn],low[maxn],stack[maxn],now,top;
bool vst[maxn];
//After tarjan these point will put into baskets(group)
int group[maxn],gcnt;

void tarjan(int n)
{
    dfn[n]=low[n]=++now;
    stack[++top]=n;
    vst[n]=true;
    for (int i=head[n];i;i=Edge[i].next)
    {
        int to=Edge[i].to;
        if (dfn[to]==0)
        {
            tarjan(to);
            low[n]=min(low[n],low[to]);
        }
        else
        {
            if (vst[to])
            {
                low[n]=min(low[n],low[to]);
            }
        }
    }
    if (low[n]==dfn[n])
    {
        group[n]=++gcnt;
        while (stack[top]!=n)
        {
            vst[stack[top]]=false;
            group[stack[top--]]=gcnt;
        }
        //make n get out of stack
        vst[n]=false;
        top--;
    }
}

int main()
{
    int n,m;
    cin>>n>>m;
    for (register int i=1;i<=m;i++)
    {
        int f,t;
        scanf("%d%d",&f,&t);
        add_edge(f,t);
    }
    for (register int i=1;i<=n;i++)
    {
        if (dfn[i]==0)tarjan(i);
    }
    for (register int i=1;i<=n;i++)
    {
        cout<<group[i]<<endl;
    }
    return 0;
}

（然而luogu的模板还是有点毒瘤的）

看一个经典例题。

例题 Luogu P2341 [HAOI2006]受欢迎的牛 |【模板】强连通分量

题目描述

每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶

牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜

欢B，B喜欢C，那么A也喜欢C。牛栏里共有N 头奶牛，给定一些奶牛之间的爱慕关系，请你

算出有多少头奶牛可以当明星。

输入格式

第一行：
两个用空格分开的整数：N和M

第二行到第M + 1行：
每行两个用空格分开的整数：A和B，表示A喜欢B

输出格式

第一行：单独一个整数，表示明星奶牛的数量

数据范围

\(10\%\)的数据\(N\leq 20, M\leq 50\)

\(30\%\)的数据\(N\leq 1000,M\leq 20000\)

\(70\%\)的数据\(N\leq 5000,M\leq 50000\)

\(100\%\)的数据\(N\leq 10000,M\leq 50000\)

可了不得这题怎么看不懂啊

现在看到这个“A受B欢迎”应当是指A向B连接一条有向边。
然后...一个强连通分量里面只要大小不为1，这里面的所有奶牛都互相喜欢。
那么我们只要缩一遍点，那么找到出度为0的强连通分量，那么所有的奶牛都会喜欢这个强连通分量里的奶牛。

所以正确处理方式就是：

  1. 缩点
  2. 找到出度为0的点。

但是注意如果要是两个出度为0的强连通分量，那可不就是没有明星了。

一类有向图dp

对于一般在有向图（不保证是DAG）上面跑DP的时候，如果不能处理后效性，
那么通常我们可以通过先缩点再拓扑排序跑DP。

例1 LuoguP3387【模板】缩点

题目背景

缩点+DP

题目描述

给定一个n个点m条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

输入格式

第一行，n,m

第二行，n个整数，依次代表点权

第三至m+2行，每行两个整数u,v，表示u->v有一条有向边

输出格式

共一行，最大的点权之和。

这个题我们可以先跑一边tarjan缩点，然后再来一发toposort，做“我为人人”类型的dp。

代码实现：

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;
template <typename Tp>
inline Tp Read()
{
    Tp num = 0;
    char ch = getchar();
    bool flag = false;
    while (!isdigit(ch))
        flag |= ch == '-', ch = getchar();
    while (isdigit(ch))
        num = (num << 1) + (num << 3) + (ch ^ 48), ch = getchar();
    return flag ? -num : num;
}
struct gragh
{
    struct edge
    {
        int from, to, next;
    };
    edge Edge[100086];
    int cnt, head[10086];
    inline void add_edge(int from, int to)
    {
        this->cnt++;
        this->Edge[this->cnt] = (edge){from, to, this->head[from]};
        this->head[from] = this->cnt;
    }
} a, b;
int n, m, val[10086];
// tarjan uses
int dfn[10086], low[10086], stack[10086], dfncnt, top;
bool instack[10086];
int group[10086], gcnt, gval[10086], In[10086];
// 缩点 解决dp后效性问题
void tarjan(int n)
{
    dfn[n] = low[n] = ++dfncnt;
    stack[++top] = n;
    instack[n] = true;
    for (int i = a.head[n]; i; i = a.Edge[i].next)
    {
        int to = a.Edge[i].to;
        if (dfn[to] == 0)
        {
            tarjan(to);
            low[n] = min(low[n], low[to]);
        }
        else
        {
            if (instack[to])
            {
                low[n] = min(low[n], low[to]);
            }
        }
    }
    if (dfn[n] == low[n])
    {
        int now;
        gcnt++;
        // gval[gcnt]=val[n];
        do
        {
            now = stack[top--];
            instack[now] = false;
            group[now] = gcnt;
            gval[gcnt] += val[now];
        } while (now != n);
    }
}
// rebuild the gragh
void rebuild()
{
    for (int i = 1; i <= a.cnt; i++)
    {
        int from = a.Edge[i].from, to = a.Edge[i].to;
        if (group[from] != group[to])
        {
            b.add_edge(group[from], group[to]);
            In[group[to]]++;
        }
    }
}
int dis[10086], ans = 0;
// dp on the DAG
void toposort()
{
    queue<int> q;
    for (int i = 1; i <= gcnt; i++)
    {
        if (In[i] == 0)
            q.push(i);
        dis[i] = gval[i];
    }
    while (!q.empty())
    {
        int from = q.front();
        q.pop();
        for (int i = b.head[from]; i; i = b.Edge[i].next)
        {
            int to = b.Edge[i].to;
            dis[to] = max(dis[from] + gval[to], dis[to]);
            In[to]--;
            if (In[to] == 0)
                q.push(to);
        }
    }
    for (int i = 1; i <= gcnt; i++)
    {
        ans = max(ans, dis[i]);
    }
}

int main()
{
    n = Read<int>(), m = Read<int>();
    for (int i = 1; i <= n; i++)
        val[i] = Read<int>();
    for (int i = 1; i <= m; i++)
    {
        a.add_edge(Read<int>(), Read<int>());
    }
    for (int i = 1; i <= n; i++)
        if (dfn[i] == 0)
        {
            tarjan(i);
        }
    rebuild();
    toposort();
    printf("%d\n", ans);
    return 0;
}

例2 LuoguP3916 图的遍历

题目描述

给出\(N\)个点，\(M\)条边的有向图，对于每个点\(v\)，求\(A(v)\),\(A(v)\)表示从点\(v\)出发，能到达的编号最大的点。

输入格式

第1 行，2 个整数\(N,M\)。

接下来\(M\)行，每行2个整数\(U_i,V_i\)，表示边\((U_i,V_i)\)。点用\(1, 2,\cdots,N\)编号。

输出格式

\(n\)个整数\(A(1),A(2),\cdots,A(N)\)。

数据范围

对于\(60\%\)的数据，\(1\leq N,K \leq 10^3\)
对于\(100\%\)的数据，\(1\leq N, M \leq 10^5\)

明显的就是一个dfs或者bfs就可以搞掉的题。

然而我们还可以通过先缩点后topo sort套dp的方式优雅AC。

代码实现：

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;
struct edge
{
    int from, to, next;
};
struct gragh
{
    edge Edge[100086];
    int cnt, head[100086];
    inline void add_edge(int from, int to)
    {
        this->cnt++;
        this->Edge[this->cnt].from = from;
        this->Edge[this->cnt].to = to;
        this->Edge[this->cnt].next = this->head[from];
        this->head[from] = cnt;
    }
};
gragh a, b;

int dfn[100086], low[100086], dfncnt, stack[100086], top;
int group[100086], gcnt, maxid[100086];
bool vst[100086];
int n, m, In[100086], dp[100086];

void tarjan(int n)
{
    dfn[n] = low[n] = ++dfncnt;
    stack[++top] = n;
    vst[n] = true;
    for (int i = a.head[n]; i; i = a.Edge[i].next)
    {
        int to = a.Edge[i].to;
        if (dfn[to] == 0)
        {
            tarjan(to);
            low[n] = min(low[n], low[to]);
        }
        else if (vst[to])
        {
            low[n] = min(low[n], dfn[to]);
        }
    }
    if (low[n] == dfn[n])
    {
        int now;
        gcnt++;
        do
        {
            now = stack[top--];
            group[now] = gcnt;
            maxid[gcnt] = max(maxid[gcnt], now);
            vst[now] = false;
        } while (now != n);
    }
}

void rebuild()
{
    for (int i = 1; i <= a.cnt; i++)
    {
        int from = a.Edge[i].from;
        int to = a.Edge[i].to;
        if (group[from] != group[to])
        {
            In[group[to]]++;
            b.add_edge(group[from], group[to]);
        }
    }
}

void toposort()
{
    queue<int> q;
    for (int i = 1; i <= gcnt; i++)
        if (In[i] == 0)
            q.push(i);
    while (!q.empty())
    {
        int from = q.front();
        q.pop();
        dp[from] = max(dp[from], maxid[from]);
        for (int i = b.head[from]; i; i = b.Edge[i].next)
        {
            int to = b.Edge[i].to;
            dp[to] = max(dp[from], dp[to]);
            if (--In[to] == 0)
                q.push(to);
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int f, t;
        scanf("%d%d", &f, &t);
        a.add_edge(t, f);
    }
    for (int i = 1; i <= n; i++)
    {
        if (dfn[i] == 0)
            tarjan(i);
    }
    rebuild();
    toposort();
    for (int i = 1; i <= n; i++)
    {
        printf("%d ", dp[group[i]]);
    }
    return 0;
}

剩下的先咕着

上一篇：Luogu P3388 【模板】割点（割顶）


下一篇：题解 P3627 【[APIO2009]抢掠计划】