POJ 2186 Popular Cows 强连通分量分解

题目链接戳这里
具体可以参考挑战程序设计竞赛二4.3节

强连通分量分解

对于一个有向图顶点的子集S,如果在S内任取2个顶点u和v,都有一条u到v的路径,则S是强连通的.任何有向图都可以分解成若干不相交的强连通分量.
强连通分量分解的思路是:

• 先从某个源点进行一次dfs,作用是给顶点打标记,而且是按后序遍历来标记.
• 得到的标记中,标号在最后打上的就是搜索树的根.此时把边都反向,再进行一次dfs
• 边反向之后,强连通分量内部的点的可达性不受影响,而内部点前往该强连通分量之外的道路因为反向被切断,从而达到分解的效果

这里有道例题,有向边a->b意味着a牛认为b牛是红人,且这种关系有传递性,即a->b, b->c, 则a->c成立,这可以理解成有向图的可达性,求被其它所有牛认为是红人的牛的总数.

分析

对于那些被所有人认为是红人的牛中,互相定然也认为对方是红人,就会形成一个强连通分量.一个有向图可能不止一个强连通分量,唯一可能成为解的集合必然是拓扑序最后的强连通分量,如图所示:

只有被所有牛崇拜才能当选

所以,问题转换成,判断最后的这个强连通分量是否与其它所有顶点都可达即可.又因为强连通分量内部肯定所有牛之间都可达,所以在最后这个强连通分量随便抓一只牛u逆向dfs,看是否能遍历完所有牛即可.

// #include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define pb push_back
const int inf = 0x3f3f3f3f, maxN = 10005;
int N, M;
// G是原图 rG是逆边之后的图
// vs存储后序遍历节点路径
// topo是每个点所在的强连通分量号 scc返回强连通分量个数
// dfs目的是得vs,rdfs目的是统计强连通个数及给顶点标号
vector<int> G[maxN], rG[maxN], vs;
int used[maxN], topo[maxN];

void add_edge(int from, int to) {
    G[from].pb(to);
    rG[to].pb(from);
}
void dfs(int v) {
    used[v] = 1;
    rep(i, 0, G[v].size())
        if (!used[G[v][i]])
            dfs(G[v][i]);
    vs.pb(v);
}
void rdfs(int v, int k) {
    used[v] = 1;
    topo[v] = k;
    rep(i, 0, rG[v].size())
        if (!used[rG[v][i]])
            rdfs(rG[v][i], k);
}
int scc() {
    mst(used, 0);
    vs.clear();
    rep(v, 0, N)
        if (!used[v])
            dfs(v);
    mst(used, 0);
    int k = 0;
    for (int i = vs.size() - 1; i >= 0; --i)
        if (!used[vs[i]])
            rdfs(vs[i], k++);
    return k;
}
void solve() {
    int n = scc();
    int u = 0, num = 0;
    rep(v, 0, N) {
        if (topo[v] == n - 1) {
            u = v;
            ++num;
        }
    }
    mst(used, 0);
    rdfs(u, 0);
    rep(v, 0, N) {
        if (!used[v]) {
            num = 0;
            break;
        }
    }
    printf("%d", num);
}
int main() {
    // freopen("data.in", "r", stdin);
    scanf("%d %d", &N, &M);
    int from, to;
    rep(i, 0, M) {
        scanf("%d %d", &from, &to);
        add_edge(from - 1, to - 1);
    }
    solve();
    return 0;
}