Tarjan 零基础详解 —— ylxmf2005的OI教程

前置芝士 & 前言

这是一篇详细介绍 Tarjan 所有常见用途的文章。需要一些前置芝士:

  1. 图论基础知识
  2. 深度优先搜索
  3. 足够的耐心和小学三年级的学历

本文章的前半部分原载与 OI-Wiki,但是我的图片被他们不知不觉的修改了,内容也删了一点(生气)。而且不知道为什么我使用的一个画图工具突然挂了,所以后面都是用的 OI-Painter 画的图,请大家见谅。

本文章的前半部分和后半部分写的时间相差接近一年,所以码风可能略有改动,不过 Tarjan 的核心代码的习惯与我题解的风格基本不会改的。还有,本文章用了三种不同的图床,不过应该不会挂掉。

本文章讲的内容(按顺序,加粗为重点内容):

  1. 割点
  2. 割边
  3. 点双联通分量
  4. 边双联通分量
  5. 强连通分量
  6. 缩点
  7. 2-SAT
  8. TarjanLCA

本文章由 ylxmf2005(QQ:2890584219)原创,不经允许,严禁转载。

割点

对于一个无向图,如果把一个点删除后这个图的极大连通分量数增加了,那么这个点就是这个图的割点(又称割顶)。

如果我们尝试删除每个点,并且判断这个图的连通性,那么复杂度会特别的高。所以要介绍一个常用的算法:Tarjan。

因为 Tarjan 可以在图上而不是只能在树上进行,所以首先声明一个在本文适用的定义:如果从 $a$ 访问到 $b$ 点,那么 $b$ 就是 $a$ 的儿子。

首先,我们上一个图:

《Tarjan 零基础详解 —— ylxmf2005的OI教程》

很容易的看出割点是 2,而且这个图仅有 2 这一个割点。

首先,我们按照 dfn 序给他打上时间戳(访问的顺序)。

《Tarjan 零基础详解 —— ylxmf2005的OI教程》

这些信息被我们保存在一个叫做 dfn 的数组中。

《Tarjan 零基础详解 —— ylxmf2005的OI教程》

还需要另外一个数组 low ,用它来存储不经过其父亲(你有多个那么就看你遍历到了哪个)能到达的最小的时间戳。

例如 $2$ 的话是 $1$,$5$ 和 $6$ 是 $3$。

然后我们开始 DFS,我们判断某个点是否是割点的根据是:对于某个顶点 $u$ ,如果存在至少一个顶点 $v$ ( $u$ 的儿子),使得 $low_v>=dfn_u$ ,即不能回到祖先,那么 $u$ 点为割点。为什么这句话是对的呢?假设当前节点是在下面,他的父亲在中间,如果他不经过他的父亲访问不到上面的点,那么这个点一定是割点了。

另外,如果搜到了自己(在环中),如果他有两个及以上的儿子,那么他一定是割点了,如果只有一个儿子,那么把它删掉,不会有任何的影响。比如下面这个图,此处形成了一个环,我们从 $1$ 走:

《Tarjan 零基础详解 —— ylxmf2005的OI教程》

我们在访问 $1$ 的儿子时候,假设先 dfn 到了 $2$,然后标记用过,然后递归往下,来到了 $4$,$4$ 又来到了 $3$,当递归回溯的时候,会发现 3 已经被访问过了,所以 $1$ 不是割点。

然后访问 $2$ ,$2$ 的儿子多了一个 $5$,加上之前访问的 $4$ 一共两个。所以 $2 $是割点。

更新 low 的伪代码如下:

如果 v 是 u 的儿子 low[u] = min(low[u], low[v]);
否则
low[u] = min(low[u], dfn[v]);

洛谷 P3388【模板】割点(割顶)

/*
    洛谷 P3388 【模板】割点(割顶)
    */
    #include <bits/stdc++.h>
    using namespace std;
    int n, m;  // n:点数 m:边数
    int dfn[100001], low[100001], inde, res;
    // dfn:记录每个点的时间戳
    // low:能不经过父亲到达最小的编号,inde:时间戳,res:答案数量
    bool vis[100001], flag[100001];  // flag: 答案 vis:标记是否重复
    vector<int> edge[100001];        // 存图用的
    void Tarjan(int u, int father)  // u 当前点的编号,father 自己爸爸的编号
    {
      vis[u] = true;             // 标记
      low[u] = dfn[u] = ++inde;  // 打上时间戳,他最小也能到自己
      int child = 0;             // 每一个点儿子数量
      for (auto v : edge[u])     // 访问这个点的所有邻居 (C++11)
      {
        if (!vis[v]) {
          child++;                       // 多了一个儿子
          Tarjan(v, u);                  // 继续
          low[u] = min(low[u], low[v]);  // 更新能到的最小节点编号
          if (father != u && low[v] >= dfn[u] &&
              !flag
                  [u])  // 主要代码
                        // 如果不是自己,且不通过父亲返回的最小点符合割点的要求,并且没有被标记过
                        // 要求即为:删了父亲连不上去了,即为最多连到父亲
          {
            flag[u] = true;
            res++;  // 记录答案
          }
        } else if (v != father)
          low[u] =
              min(low[u], dfn[v]);  // 如果这个点不是自己,更新能到的最小节点编号
      }
      if (father == u && child >= 2 &&
          !flag[u])  // 主要代码,自己的话需要 2 个儿子才可以,如果这个点已经是割点,那么不能重复计算。
      {
        flag[u] = true;
        res++;  // 记录答案
      }
    }
    int main() {
      cin >> n >> m;                // 读入数据
      for (int i = 1; i <= m; i++)  // 注意点是从 1 开始的
      {
        int x, y;
        cin >> x >> y;
        edge[x].push_back(y);
        edge[y].push_back(x);
      }                             // 使用 vector 存图
      for (int i = 1; i <= n; i++)  // 因为 Tarjan 图不一定连通
        if (!vis[i]) {
          inde = 0;      // 时间戳初始为 0
          Tarjan(i, i);  // 从第 i 个点开始,父亲为自己
        }
      cout << res << endl;
      for (int i = 1; i <= n; i++)
        if (flag[i]) cout << i << " ";  // 输出结果
      for (int i = 1; i <= n; i++) cout << low[i] << endl;
      return 0;
    }

割边

和割点差不多,还叫做割桥。对于一个无向图,如果删掉一条边后图中的连通分量数增加了,则称这条边为桥或者割边。如下图,割边有:${1,2} , {2,5}$。

《Tarjan 零基础详解 —— ylxmf2005的OI教程》

和割点差不多,只要改一处: $low_v>dfn_u$ 就可以了,而且不需要考虑根节点的问题。

割边是和是不是根节点没关系的,原来我们求割点的时候是指点 $v$ 是不可能不经过父节点 $u$ 为回到祖先节点(包括父节点),所以顶点 $u$ 是割点。如果 $low_v=dfn_u$ 表示还可以回到父节点,如果顶点 $v$ 不能回到祖先也没有另外一条回到父亲的路,那么 $u-v$ 这条边就是割边。

#include<bits/stdc++.h>
using namespace std;
int n, m;
int dfn[100001], low[100001], index, res, tot;
bool vis[100001], cut[500001];
pair <int, int> edge[500001]; //边对应的两个点 
vector <pair<int,int> > G[100001]; // 新增一个元素记录边的编号 
void Tarjan(int x, int fa){
    vis[x] = true; low[x] = dfn[x] = ++index;
    int child = 0;
    for (int i = 0; i < G[x].size(); i++){
        int y = G[x][i].first, z = G[x][i].second;
        if (!vis[y]){
            child++; Tarjan(y,x);
            low[x] = min(low[x], low[y]);
            if (low[y] > dfn[x] && !cut[x]) cut[z] = true, res++;
        }else if(y != fa) low[x] = min(low[x], dfn[y]);
    }
}
int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++){
        int x, y; scanf("%d%d", &x, &y);
        G[x].push_back(make_pair(y, ++tot)); G[y].push_back(make_pair(x, tot));
        edge[tot] = make_pair(x, y);
    }
    for (int i = 1; i <= n; i++)
        if (!vis[i]) index = 0, Tarjan(i, i);
    printf("%d\n", res);
    for (int i = 1; i <= m; i++)
        if (cut[i]) printf("%d %d\n", edge[i].first, edge[i].second);
    return 0;
}

点双联通分量

前方高能!虽然很难,但务必掌握。

点双联通图的定义是:没有割点的无向联通图。如图,该图有 $3$ 个点联通分量(不知道联通分量出门左转百度):${1,2},{2,5},{2,3,4}$(不唯一,比如 $2,5$ 可以换成 $2,3$)。

《Tarjan 零基础详解 —— ylxmf2005的OI教程》

判断一个图是否是点双联通图只要照着定义跑一边割点就可以判断了,但是大多数题目都是让我们求出点联通分量。

  1. 不超过两个点的子图一定点双联通,因为他不会有割点,而三个点的话只要组成一条链,中间那个点就是割点。

  2. 如果有超过两个点的图,只要这个图的所有点都包含在一个简单环中,那么他一定是点联通图。

扩展到点联通分量,点联通分量一定要是极大的。如果一个点能回到他的上面即为他的祖宗,那么这就是一个简单环,但是如果还有一个点还能回到前者上面的上面,即为前者祖宗的祖宗,那么我们选择后者肯定比前者优秀,因为后者包含的范围更大。一句话总结:子孙没有指向这个点的祖先的边,却有指向这个点的边

而且呢,必须只包含在一个环中,不能是多个,如下图,如果令所有的点为点双联通分量,显然他们在两个环中,$2$ 就是割点。

《Tarjan 零基础详解 —— ylxmf2005的OI教程》

我们开一个栈,如果遇到一个点是第一次访问,那么我们把它压入栈中。如果当前的点与他的祖先组成了割点,那么我们就把中间过程的所有点弹出来,直到他的祖先被弹出为止。我们弹出的所有点就是一个点双联通分量。

为什么是这样做是对的?因为割点是在回溯中判断的,我们越早访问的点,回溯的越晚,图的规模越小。反之同理。

结合下面模拟和代码感性理解一下。

《Tarjan 零基础详解 —— ylxmf2005的OI教程》

访问 $1$,访问 $2$ ,访问 $5$,$5$ 返回 $2$,$2$ 访问 $3$,$3$ 访问 $4$,$4$ 访问 $2$,$2$ 已经访问过了,不继续扩展,于是 $2$ 先返回到 $1$,发现 $2$ 是割点,加入点双联通分量 ${2,5}$,然后从 $2$ 返回到 $4$,$4$ 返回到 $3$,返回到 $2$,$2$ 返回到 $1$,发现 $2$ 还是割点,于是加入点双联通分量 ${2,3,4}$。还有一个点双联通分量 ${1,2}$,怎么办?额,我们只从 $1$ 开始找,从每个点开始进行 Tarjan 就好了。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, dfn, cnt, dfn[N], low[N], cut[N];
vector <int> G[N], ans[N];
stack <int> st; 
void Tarjan(int x, int fa) {
    dfn[x] = low[x] = ++dfn; st.push(x);
    int child = 0 ;
    for (int i = 0; i < G[x].size(); i++) {
        int y = G[x][i];
        if(!dfn[y]) {
            child++; Tarjan(y, x); low[x] = min(low[y] , low[x]);
            if(low[y] >= dfn[x]) {
                cut[x] = 1; ans[++cnt].push_back(x);
                while(x!=st.top()) ans[cnt].push_back(st.top()), st.pop();  //统计答案          
            }   
        }else if (dfn[x] > dfn[y] && y != fa) low[x] = min(dfn[y], low[x]); //y能走到x(一个环就有可能)
    }
    if (fa == 0 && child == 1) cut[x] = 0; //2个点,我们上面会误判 x 为割点。
    if (fa == 0 && child == 0) G[++cnt].push_back(x); //一个点
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++){
            int x, y; scanf("%d%d", &x, &y);
            G[x].push_back(y); G[y].push_back(x);
    }
    for (int i = 1; i <= n; i++) if(!dfn[i]) Tarjan(i, 0);
    printf("%d\n", cnt);
    for (int i = 1; i <= cnt; i++)
         for (int j = 0; j < ans[i].size(); j++)
            printf("%d%c", ans[i][j], (j == ans[i].size() - 1 ? '\n' :' '));
    return 0;
}

边双联通分量

顾名思义,边双联通分量就是没有割边的无向联通图。如下图,边双联通分量是且仅是整个图。

《Tarjan 零基础详解 —— ylxmf2005的OI教程》

相比于点双联通分量,边双联通分量就很简单了。

进行一次 Tarjan 求出所有的割边,把这些割边 "删掉"(就是在求联通分量的时候不访问),然后统计所有的联通分量就是边双联通分量了。简单吧?为什么边双联通分量没有点双联通分量那么难呢?因为一条边最多存在于一个子图中,而一个点可以存在于多个子图中。所以我们可以删割边,不能删割点了。

#include<bits/stdc++.h>
using namespace std;
int n, m;
int dfn[100001], low[100001], index, tot;
bool vis[100001], cut[500001];
pair <int, int> edge[500001]; //边对应的两个点 
vector <pair<int,int> > G[100001]; // 新增一个元素记录边的编号 
void Tarjan(int x, int fa){
    vis[x] = true; low[x] = dfn[x] = ++index;
    int child = 0;
    for (int i = 0; i < G[x].size(); i++){
        int y = G[x][i].first, z = G[x][i].second;
        if (!vis[y]){
            child++; Tarjan(y,x);
            low[x] = min(low[x], low[y]);
            if (low[y] > dfn[x] && !cut[x]) cut[z] = true;
        }else if(y != fa) low[x] = min(low[x], dfn[y]);
    }
}
vector <int> ans; 
void dfn(int x){//求图中的联通分量 

    for (int i = 0; i < G[x].size(); i++){
        int y = G[x][i].first, z = G[x][i].second;
        if (vis[y] || cut[z]) continue; //不重复不是割点 
        vis[y] = 1; ans.push_back(y);
        dfn(y); 
    } 
} 
int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++){
        int x, y; scanf("%d%d", &x, &y);
        G[x].push_back(make_pair(y, ++tot)); G[y].push_back(make_pair(x, tot));
        edge[tot] = make_pair(x, y);
    }
    for (int i = 1; i <= n; i++)
        if (!vis[i]) index = 0, Tarjan(i, i);
    memset(vis, 0, sizeof(vis)); //节约空间 
    for (int i = 1; i <= n; i++)
        if (!vis[i]){
            vis[i] = 1; 
            ans.clear();  ans.push_back(i); 
            dfn(i);
            for (int i = 0; i < ans.size(); i++) printf("%d%c", ans[i], (i == ans.size() - 1 ? '\n' : ' '));
        }
    return 0;
}

强连通分量

强连通分量与点双联通分量本质上是一模一样的,不要以为强连通分量难,只要你能看懂点双联通分量,相信你能看懂强连通分量的(正是因为我们讲了点双联通分量,所以强连通分量才讲解的那么短)。

所谓的强连通图,就是一个有向图中,任意两个点互相都能到达,那么强连通分量就是极大的强连通图了。如下图,强联通分量有:${1,2,3},{4},{5}$。

《Tarjan 零基础详解 —— ylxmf2005的OI教程》

如果你学会了点双联通分量,并且是个爱思考的孩子,那么相信你已经大概知道如何求了。如上面那张图,$1, 2, 3$ 所有的点都在一个有向的简单环中,$4$ 和 $5$ 都是一个孤立的点。那么我们可以直接大胆下结论:

  1. 只有一个点的子图一定是强连通的子图
  2. 一个强连通子图中的所有点,一定在一个简单环内(有向图中的简单环是由回祖路造成的,回祖路是从自己连向自己的祖先的边)。

我们要求的是强连通分量,按照之前的套路,还是要要满足一个点的联通子图中:子孙没有指向这个点的祖先的边,却有指向这个点的边

我们还是需要一个栈,遇到一个点被访问过,那么我们把它加入栈,如果遇到的这个点已经被访问过,那么它们中间的子图都是强连通的(同一个节点第一次被访问的位置到第二次被访问位置中间所有的点,包括被访问两次的点本身)。但是我们不确定这个子图是不是极大的,因为我们并不是和点双联通分量用割点方法判断的,你想想,既然不用割点判断,那么我们为什么要进行 Tarjan 呢?

不要忘记了我们的 dfnlow 数组,因为之前提到需要满足 子孙没有指向这个点的祖先的边,却有指向这个点的边 所以我们看看它不经过自己,能不能到自己的祖宗,为什么只判断自己就够了?因为如果下面的点能到这个点的祖宗,那么自己可以走到那个点后再到自己的祖宗嘛(有点绕口令)。所以,我们只需要判断 dfn[x] == low[x] 就可以知道是不是一个强连通分量了。

相信你会写了,因为还有一些细节,不会写的看代码(代码没讲过的地方的注释很详细了,如果你不会点双联通分量也看不懂这里的讲解还是去上面学一下吧)

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, num, cnt, dfn[N], low[N], cut[N], res, vis[N];
vector <int> G[N], ans[N];
stack <int> st; 
void Tarjan(int x) {
    dfn[x] = low[x] = ++num; st.push(x); vis[x] = 1; 
    int child = 0 ;
    for (int i = 0; i < G[x].size(); i++) {
        int y = G[x][i];
        if(!dfn[y]) {
            child++; //child没用 打模板习惯打上去了 
            Tarjan(y); low[x] = min(low[y] , low[x]);       
        }else if(vis[y]) low[x] = min(dfn[y], low[x]); //必须要判断它的 vis,因为我们下面可能会取消vis标记 
    }
    if (dfn[x] == low[x]){
        int y = -1; cnt++;
        while (x != y){
            ans[cnt].push_back(y = st.top()); vis[st.top()] = 0;    // 以后可能还要用到这个点的,因为一个点可能在两个强联通分量中。
            st.pop();
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++){
            int x, y; scanf("%d%d", &x, &y);
            G[x].push_back(y); 
    }
    for (int i = 1; i <= n; i++) if(!dfn[i]) Tarjan(i);
    printf("%d\n", cnt);
    for (int i = 1; i <= cnt; i++)
         for (int j = 0; j < ans[i].size(); j++)
            printf("%d%c", ans[i][j], (j == ans[i].size() - 1 ? '\n' :' '));
    return 0;
}

缩点

缩点可不是一个高大上的东西。缩点就是把有向图每个强连通分量缩成若干个超级点。如下图,我们可以把这个图缩成三个点:$A,B,C$,$A$ 对应 $1 \ 2 \ 3$,$B$ 对应 $4$,$C$ 对应 $5$。缩点后的图具有一个性质:一个有向无环图(DAG),我们可以在这个图上进行很多操作。所以缩点是 Tarjan 最实用的算法了,一般题目是以某个算法为主(常是 DP),以缩点为辅。所以只学好缩点是做不出题的,还要学一下其他的算法。下面的 2-SAT 就用到了缩点(那道题的难点在找规律)。

《Tarjan 零基础详解 —— ylxmf2005的OI教程》

我们上面的代码,已经求出了所有的强连通分量和它们包括的点,所以直接将每个强连通分量转成点就可以了。如果两个点之间右边,那么它们所在的强连通分量,也就是我们的超级点也会有边,这样的话可能有重边,但是边权不一定相同,边权视情况而定。具体实现见代码。

如果你学会了强连通分量,相信这对你很简单。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, num, cnt, dfn[N], low[N], cut[N], res, vis[N], tot, color[N];
vector <int> G[N], ans[N], G2[N];
stack <int> st; 
void Tarjan(int x) {
    dfn[x] = low[x] = ++num; st.push(x); vis[x] = 1; 
    int child = 0 ;
    for (int i = 0; i < G[x].size(); i++) {
        int y = G[x][i];
        if(!dfn[y]) {
            child++; //child没用 打模板习惯打上去了 
            Tarjan(y); low[x] = min(low[y] , low[x]);       
        }else if(vis[y]) low[x] = min(dfn[y], low[x]); //必须要判断它的 vis,因为我们下面可能会取消vis标记 
    }
    if (dfn[x] == low[x]){
        int y; cnt++;
        do{
            ans[cnt].push_back(y = st.top()); vis[y] = 0; color[y] = cnt;
            // 以后可能还要用到这个点的,因为一个点可能在两个强联通分量中。
            st.pop();
        }while (x != y);
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++){
            int x, y; scanf("%d%d", &x, &y);
            G[x].push_back(y); 
    }
    for (int i = 1; i <= n; i++) if(!dfn[i]) Tarjan(i);

    for (int i = 1; i <= n; i++) {//这里不是 O(n^2) 而是 O(2 * n) 的 
        for (int j = 0; j < G[i].size(); j++){
                if(color[i] != color[G[i][j]]) //不能自己连自己 
                    G2[color[i]].push_back(color[G[i][j]]); //DAG
        } 

    } 
    for (int i = 1; i <= cnt; i++){
        printf("%d:", i);
        for (int j = 0; j < G2[i].size(); j++)
            printf(" %d", G2[i][j]);
        puts(""); 
    }

    return 0;
}

为了感受一下缩点的强大,我们一起来做一道入门题(不会 DAG 上 DP 者左转百度):

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

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


这道题不是什么最大生成树,因为它可以重复经过一个点。这可怎么办呢?下面展示一下缩点题目的思考过程:

  1. 这道题图论(最大生成树)好像不可做。
  2. 嗯,有有向图的条件,可以缩点?
  3. 缩点后能用什么算法?
  4. 想了一段时间:哦,好像在 DAG 上 DP 就行了。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 4, M = 1e5 + 5; 
int n, m, tot, cnt;
int w[N], dfn[N], low[N], vis[N], color[N], in[N], dp[N], sum[N];
stack <int> st;
vector <int> G[N], G2[N];
queue <int> q;
void Tarjan(int x){
    st.push(x); vis[x] = 1;
    dfn[x] = low[x] = ++tot;
    for (int i = 0; i < G[x].size(); i++){
        int y = G[x][i];
        if (!dfn[y]){
            Tarjan(y); low[x] = min(low[y], low[x]);
        } else if (vis[y]) low[x] = min(dfn[y], low[x]);
    }
    if (dfn[x] == low[x]){
        int y; cnt++;
        do{
            y = st.top(); st.pop(); //dp[y] = w[y];
            vis[y] = 0; color[y] = cnt;
        }while(x != y); 
    }
}
void solve(){
    for (int i = 1; i <= cnt; i++)
        if(!in[i]) q.push(i), dp[i] = sum[i];
    while (!q.empty()){
        int x = q.front(); q.pop();
        for (int i = 0; i < G2[x].size(); i++){
            int y = G2[x][i];
            dp[y] = max(dp[y], dp[x] + sum[y]);
            if (!--in[y]) q.push(y);
        }
    }
    printf("%d\n", *max_element(dp + 1, dp + cnt + 1));
}
int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
    for (int i = 1; i <= m; i++){
        int x, y; scanf("%d%d", &x, &y);
        G[x].push_back(y); 
    }
    for (int i = 1; i <= n; i++) if (!dfn[i]) Tarjan(i);
    for (int i = 1; i <= n; i++) sum[color[i]] += w[i];
    for (int x = 1; x <= n; x++)
        for (int i = 0; i < G[x].size(); i++){
            int y = G[x][i];
            if (color[x] != color[y]) {
                G2[color[x]].push_back(color[y]);
                in[color[y]]++;
            }
        }
    solve();
    return 0;
}

2-SAT

前置芝士:上面的所有内容与自己探索的信心

前方真正高能(这里是省选才考的内容,可以不学习)这道题理解题意就是一个难点,为了方便大家理解题意,我们把题目转换成了一个模型:

一天,小 Y 去给他的 GF 买饭,他一共有 $n$ 个 GF(假设有 $3$ 个),每个 GF 有 $2$ 个要求,满足其中一个即可:

GF 1 的要求:

  1. 不要肉
  2. 要菜

GF 2 的要求:

  1. 要肉
  2. 要菜

GF 3 的要求:

  1. 不要肉
  2. 不要菜

小 Y 想得到 GF 的欢心,但是他的 GF 的问题实在是太刁钻了,所以小 Y 希望满足每一个女朋其中一个的条件。显然,这个问题有两个个答案:要菜,不要肉和不要肉,要菜。

我们发现,每个 GF 的条件只有 2 个,实际上,条件 $ \ge 3$ 的时候已经被证明了是 NP 问题,只能暴力求解(我可不证明啊)。但是,对于条件只有 $2$ 个 的可以用 Tarjan 求解。注意: 条件 $ \ge 3$ 是指的每个 GF 的条件$ \ge 3$,而不是条件的总数。条件的总数可能有多个。

我们不妨设 要肉为 $a$,不要肉为 $-a$,要菜为 $b$,不要菜为 $-b$。那么我们对于每一个 GF,如果他一个条件不满足,那么另一个条件就必须满足。例如 GF 1,如果只满足她的一个条件,那么可以满足:$-a$ 和 $b$ 或 $a$ 和 $-b$。

我们发现,对于每个 GF,将她的一个条件取反,与另一个条件连一条有向边( $-a$ 的编号 实际上是 $a + 3$ 即为 $a + n$),会形成一个有 $2 \times 3$($2 \times n$)个节点的图,如下图:

《Tarjan 零基础详解 —— ylxmf2005的OI教程》

可以发现,无解当且仅当 $a$ 与 $-a$ 或 $b$ 与 $-b$ 在一个强连通分量中,反之有解。

然后,我们将图缩点,如下图。仔细观察这个图,发现我们构成的是一张拓扑图。这张拓扑图中,如果 $x$ 可以到达 $y$,那么选择则 $x$ 的话,$y$ 也必须选择(仔细想一想)。那么,你可以利用强连通分量的时间戳来得到反向的拓扑序

《Tarjan 零基础详解 —— ylxmf2005的OI教程》

但是,对于一组条件,可能会有多组解同时成立。要怎样判断给每个变量赋的值是否恰好构成一组解呢?我们发现,可以用超级点的编号来得到反向的拓扑序(Tarjan真是一个神奇的东西)。那么结论就是:对于有 $a$ 与 $-a$ 的强连通分量中,我们选择拓扑序较大的点。

相信你没有理解,看一下详细的代码吧。

#include <bits/stdc++.h>
using namespace std;
const int N = (1e6 + 10) * 2;
int low[N], dfn[N], color[N];
bool vis[N];
stack<int>st;
int n, m, tot, cnt;
vector <int> G[N];
void Tarjan(int x)
{
    low[x] = dfn[x] = ++tot;
    st.push(x); vis[x] = 1;
    for (int i = 0; i < G[x].size(); i++){
        int y = G[x][i];
        if (!dfn[y]){
            Tarjan(y);
            low[x] = min(low[y], low[x]);
        }else if(vis[y]) low[x] = min(low[y], low[x]);
    }
    if (low[x] == dfn[x]){
        int y; cnt++;
        do{
            y = st.top(); st.pop();
            vis[y] = 0; color[y] = cnt;
        }while(x!=y);
    }
}
bool check()
{
    for (int i = 1; i <= 2 * n; i++) if (!dfn[i]) Tarjan(i); //Tarjan找强连通分量 
    for (int i = 1; i <= n; i++) if(color[i] == color[i + n]) return 0; //a和-a在同一个强连通分量,无解。 
    return 1;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++){    //用a表示条件a,a+n表示条件-a。
        int a, b, x, y; scanf("%d%d%d%d", &a, &x, &b, &y);
        G[a + (x ^ 1) * n].push_back(b + y * n); //连边(-a,b) 
        G[b + (y ^ 1) * n].push_back(a + x * n); //连边(-b,a) 
    }
    if(check())
    {
        puts("POSSIBLE");
        for (int i = 1; i <= n; i++) printf("%d ", color[i] > color[i + n]);
    }else puts("IMPOSSIBLE");
    return 0;
}

LCA

前置芝士:并查集和 LCA 的概念。

放心,这篇文章没有上一篇那么难懂了(虽然也是省选算法,可以不理解,倍增就可以了)。

Tarjan 求 LCA 是所有求 LCA 的方法中最快的,是离线算法(离线算法是指首先读入所有的询问(求一次LCA叫做一次询问),然后重新组织查询处理顺序以便得到更高效的处理方法。)。而且预处理和查询的常数都是最小的,复杂度是常数较大的 $O(n + m + q)$(我们要先存输入,并且用到了并查集)。对于数据范围大,查询又多的题目有奇效。下面直接讲算法:

每进入一个节点 $x$ 的 Tarjan,就把当前的树看作以 $x$ 为根节点的子树,再搜索其他的节点。每搜索完一个点后,如果该点和另一个已搜索完点 $y$ 为需要查询 LCA 的一对点,则这两点的 LCA 为 $y$ 的现在的祖先。

  1. 建图,我们用两个 vector 来保存这颗树,与所有的查询(查询 $x$ 与 $y$,那么给 $x$ 和 $y$ 连一条双向边,用数组存浪费空间会 MLE)。
  2. 从根节点开始 Tarjan。
  3. 在递归函数中,先将自己的父亲设置为自己(把当前的树看作以自己为根的子树,我们令当前点为 $x$),然后找与他相邻的点,如果没有被访问,那么就对这个点 Tarjsan,结束后把这个点的子树与 $x$ 这个点合并,使用并查集。
  4. 每搜索完一个点后,判断它能不能与一个点构成的点对是查询的 LCA,用 vector $O(1)$ 判断。如果是的话算出答案保存在答案数组中。
  5. 在 Tarjan结束后输出答案。

相信你看懂了(怎么又是这句话),但是细心的小朋友可以发现,"如果是的话算出答案保存在答案数组中" 这句话中的 算出答案的方法我还没介绍呢。没关系,用并查集找爹就可以了。还有一个问题是:我们输出要按照输入的顺序,我们可以在 vector 加上一个关键字。具体见代码(洛谷卡 vector,所以这个算法比倍增还慢,可以换成链式前向星或者吸一口氧气就比倍增快多了,反正我懒得改,吸了口氧气)。

#include <bits/stdc++.h>
using namespace std;
const int N = 500000 + 5; 
int n, q, s, vis[N], ans[N];
int f[N];
vector <int> G[N];
vector <pair<int, int> > ask[N]; 
int find(int k){
    if(f[k] == k) return f[k];
    return f[k] = find(f[k]);
}
void merge(int a,int b){
    int A = find(a), B = find(b);
    if(A != B) f[B] = A;
}
void Tarjan(int x){
    f[x] = x; vis[x] = 1;
    for (int i = 0; i < G[x].size(); i++){
        int y = G[x][i]; 
        if (!vis[y]){
            Tarjan(y); merge(x, y);
        }
    } 
    for (int i = 0; i < ask[x].size(); i++){
        int y = ask[x][i].first, z = ask[x][i].second;
        if(vis[y]) ans[z] = find(y);
    }
}
int main(){
    scanf("%d%d%d", &n, &q, &s);
    for (int i = 1; i < n; i++){
        int x, y; scanf("%d%d", &x, &y);
        G[x].push_back(y); G[y].push_back(x);
    }
    for (int i = 1; i <= q; i++){
        int x, y; scanf("%d%d", &x, &y);
        ask[x].push_back(make_pair(y, i)); ask[y].push_back(make_pair(x, i));
    }
    Tarjan(s);
    for (int i = 1; i <= q; i++)
        printf("%d\n", ans[i]);
    return 0;
}

撒花!感谢你用心看完了这么长的一篇讲解!不懂或认为有待改进的地方可以联系我的 QQ:2890584219。

点赞
  1. ylxmf2005说道:
    1. ylxmf2005说道:

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据