POJ 3180 The Cow Prom 题解《挑战程序设计竞赛》

POJ 3180 The Cow Prom 

奶牛圆舞：N头牛，M条有向绳子，能组成几个歌舞团？要求顺时针逆时针都能带动舞团内所有牛。

4.3成为图论大师之路 

强连通分量分解

睡不着，刷一题解解闷。

所谓能带动，就是舞团构成一个强连通分量，就是赤裸裸的SCC。

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;
#define MAX_V 10000

int V;                      // 顶点数
vector<int> G[MAX_V];       // 图的邻接表表示
vector<int> rG[MAX_V];      // 反向图
vector<int> vs;             // 后序遍历顺序的顶点列表
bool used[MAX_V];           // 访问标记
int cmp[MAX_V];             // 所属强连通分量的拓补序

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

void dfs(const int &v)
{
    used[v] = true;
    for (int i = 0; i < G[v].size(); ++i)
    {
        if (!used[G[v][i]])
            dfs(G[v][i]);
    }
    vs.push_back(v);
}

void rdfs(const int &v, const int &k)
{
    used[v] = true;
    cmp[v] = k;
    for (int i = 0; i < rG[v].size(); ++i)
    {
        if (!used[rG[v][i]])
            rdfs(rG[v][i], k);
    }
}

int scc()
{
    memset(used, 0, sizeof(used));
    vs.clear();
    for (int v = 0; v < V; ++v)
    {
        if (!used[v])
            dfs(v);
    }
    memset(used, 0, sizeof(used));
    int k = 0;
    for (int i = vs.size() - 1; i >= 0; --i)
    {
        if (!used[vs[i]])
            rdfs(vs[i], k++);
    }

    return k;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    int m;
    scanf("%d%d", &V, &m);
    for (int _ = 0; _ < m; ++_)
    {
        int from, to;
        scanf("%d%d", &from, &to);
        --from;
        --to;
        add_edge(from, to);
    }
    int n = scc();
    vector<int> count(n, 0);
    for (int v = 0; v < V; ++v)
    {
        ++count[cmp[v]];
    }
    int ans = 0;
    for (int i = 0; i < n; ++i)
    {
        if (count[i] >= 2)
        {
            ++ans;
        }
    }
    printf("%d\n", ans);
#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3180 The Cow Prom 题解《挑战程序设计竞赛》