ACM模版

描述

题解

十分好的一道题，强连通分量 + 缩点 + 并查集。这也是我做过的第一道关于强连通分量的题，所以我肯定需要找一下大牛们的题解进行参考，找到了一个大神的博客，讲得细致至极，感觉很受用，分享给大家。 mengxiang000000 ‘s blog

我断然无法写得比大神的题解更加详细，但是总结的说一下。首先求得强连通分量，然后进行缩点，形成一张新的图，标记缩点部分的 flag[]=1 ，表示此处是强连通分量，然后呢，进行并查集合并，合并后会形成若干个连通图，这些连通图有两类，一个是包含强连通分量的，一种是不包含的，不包含强连通分量的连通图需要建立 x−1 条通道，而包含的则需要 x 条，这里的 x 表示该连通图的结点数。

也就是说，最后的结果其实是所有的城市数 n <script type="math/tex" id="MathJax-Element-227">n</script> 减去不包含强连通分量的连通图的数目。

再次，膜拜大佬…… mengxiang000000 ‘s blog

代码

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int MAXN = 1e5 + 10;

int n, m;
int id_val, cnt, top, ans;
int F[MAXN];    // 并查集
int id[MAXN];
int id_cnt[MAXN];
int flag[MAXN];
int dfn[MAXN];
int low[MAXN];
int vis[MAXN];
int sta[MAXN];
vector<int> vi[MAXN];

int find(int x)
{
    if (F[x] == x)
    {
        return x;
    }
    else
    {
        return F[x] = find(F[x]);
    }
}

void Tarjan(int u)
{
    sta[++top] = u;
    dfn[u] = low[u] = cnt++;
    vis[u] = 1;
    for (int i = 0; i < vi[u].size(); i++)
    {
        int v = vi[u][i];
        if (vis[v] == 0)
        {
            Tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        if (vis[v] == 1)
        {
            low[u] = min(low[u], low[v]);
        }
    }
    if (dfn[u] == low[u])
    {
        id_val++;
        do
        {
            id[sta[top]] = id_val;
            vis[sta[top]] = -1;
        }
        while (sta[top--] != u);
    }
}

void solve()
{
    for (int i = 1; i <= n; i++)
    {
        if (vis[i] == 0)
        {
            Tarjan(i);
        }
    }

    for (int i = 1; i <= id_val; i++)
    {
        F[i] = i;
    }
    for (int i = 1; i <= n; i++)
    {
        id_cnt[id[i]]++;
    }
    for (int i = 1; i <= id_val; i++)
    {
        if (id_cnt[i] > 1)  // 说明这是一个强连通分量
        {
            flag[i] = 1;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < vi[i].size(); j++)
        {
            int u = id[i];
            int v = id[vi[i][j]];
            if (u != v)
            {
                int u_ = find(u);
                int v_ = find(v);
                if (u_ != v_)
                {
                    F[v_] = u_;
                    flag[u_] += flag[v_];
                }
            }
        }
    }

    for (int i = 1; i <= id_val; i++)
    {
        if (F[i] == i)
        {
            if (flag[i] == 0)
            {
                ans--;
            }
        }
    }
}

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}

void init()
{
    for (int i = 1; i <= n; i++)
    {
        vi[i].clear();
    }

    top = -1;
    cnt = 1;
    id_val = 0;
    ans = n;
    memset(id_cnt, 0, sizeof(id_cnt));
    memset(id, 0, sizeof(id));
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(vis, 0, sizeof(vis));
    memset(sta, 0, sizeof(sta));
    memset(flag, 0, sizeof(flag));
}

int main()
{
    while (~scanf("%d%d", &n, &m))
    {
        init();

        int a, b;
        for (int i = 0; i < m; i++)
        {
            scan_d(a), scan_d(b);
            vi[a].push_back(b);
        }

        solve();

        printf("%d\n", ans);
    }

    return 0;
}