Table of contents

算法详解

花了一点小时间入门了 kosaraju 算法。
记得之前在一篇博文中提到过,ACM中求强联通分量的常见算法有三种:

  1. 暴力
  2. Tarjan
  3. Kosaraju

其中暴力和 Kosaraju 算法在求强联通分量的同时,可以直接输出可行解,而Tarjan则需要通过额外的拓扑排序来得出可行解。

简单说一下 Kosaraju 的基本思路:
Kosaraju算法主要通过一个非常显然的性质来求强联通分量的。

对于一个强联通分量,将它的所有边反向,那么它依然是一个强联通分量。

因此,我们通过两边dfs,第一遍dfs求出整张图的拓扑序,第二遍dfs按照拓扑序通过反向边进行拓展。
这个地方就非常巧妙。因为在按照拓扑序遍历的过程中,对于一个点,如果它是一个强联通分量的一个点,那么除开原先遍历标记过点,必然会存在拓扑序在该点之后但仍然指向该点的一个点。

好难表达,yy很容易

题解

题意:
有一群牛,给你很多个关系,一对关系 a -> b 表示 a 认为 b 是肥宅,问被所有牛公认为肥宅的牛有几头。

思路:
题意即 在拓扑序排最后一个强联通分量的数量。
注意,原图可能不联通,不联通根据题意输出0。

AC Code

#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef long long ll;
const int inf = 0x3f3f3f3f;
const int max_v = 1e4 + 5;

int v_num, num;
vector<int> G[max_v], rG[max_v], vs;
bool vis[max_v];
int color[max_v];

void dfs(int u)
{
    vis[u] = true;
    int sz = G[u].size();
    for (int i = 0; i < sz; i++)
        if (!vis[G[u][i]])
            dfs(G[u][i]);
    vs.push_back(u);
}

void rdfs(int u, int scc)
{
    vis[u] = true;
    color[u] = scc;
    int sz = rG[u].size();
    for (int i = 0; i < sz; i++)
        if (!vis[rG[u][i]])
            rdfs(rG[u][i], scc);
}

int kosaraju()
{
    memset(vis, false, sizeof vis);
    vs.clear();
    for (int v = 1; v <= v_num; v++)
        if (!vis[v])
            dfs(v);
    memset(vis, false, sizeof vis);
    int scc = 0;
    num = 0;
    for (int i = vs.size() - 1; i >= 0; i--) {
        if (!vis[vs[i]])
            rdfs(vs[i], scc++);
    }
    int res = 0, u;
    for (int i = 1; i <= v_num; i++) {
        if (color[i] == scc - 1) {
            u = i;
            res++;
        }
    }
    memset(vis, false, sizeof vis);
    rdfs(u, 0);
    for (int i = 1; i <= v_num; i++)
        if (!vis[i])
            return 0;
    return res;
}

void addEdge(int from, int to)
{
    G[from].push_back(to);
    rG[to].push_back(from);
}

int main()
{
    int m, u, v;
    while (scanf("%d %d", &v_num, &m) != EOF) {
        for (int i = 1; i <= v_num; i++)
            G[i].clear(), rG[i].clear();
        while (m--) {
            scanf("%d %d", &u, &v);
            addEdge(u, v);
        }
        printf("%d\n", kosaraju());
    }
    return 0;
}

发表评论

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

Related Posts

强联通分量

HDU 6165 FFF at Valentine

好烦,感觉自己的图论知识都有了,但是一旦写起来还是非常欠缺…… 什么时 Read more…

强联通分量

HDU 6073 Matching In Multiplication

今天多校的第一锅…… 这套题真是神奇,明明都是Claris出的,涉及图 Read more…

强联通分量

HDU 5452 Minimum Cut

本来以为是一道好题…… 没想到xjb被我水过去了…… 题目看不大懂去找 Read more…