poj 1236(强连通分量分解模板题)-白红宇

poj 1236(强连通分量分解模板题)

阅读量：793 次

发布时间：2023-03-03

本文共 2940 字，大约阅读时间需要 9 分钟。

问题解析

将问题抽象为有向图模型后，问题可以分为以下两个部分解决：

问题1：最少需要选多少个顶点作为初始点

找到所有强连通分量：每个强连通分量是一个顶点集合，内部任意两点之间都可以相互到达。

构建有向无环图（DAG）：将每个强连通分量缩成一个点。

统计DAG中的入度为0的点数：这些点必须作为初始点，才能覆盖整个DAG。

问题2：最少需要添加多少条边

统计DAG中的入度为0点数（k）和出度为0点数（m）。

计算最大值：问题2的答案为max(k, m)，因为需要连接这些无法到达的点。

代码实现

#include 
   
    
#include 
    
     
#include 
     
      
#include 
      
       
using namespace std;
#define pb push_back
#define mem(a, b) memset(a, b, sizeof(a))
const int maxn = 100 + 50;
int n;
int num;
struct Edge {
    int to;
    int next;
} G[maxn * maxn < 1];
void addEdge(int u, int v) {
    G[num] = {v, head[u]};
    head[u] = num++;
}
struct SCC {
    int col[maxn];
    int in[maxn];
    int out[maxn];
    bool vis[maxn];
    vector
       
         vs;
    void DFS(int u) {
        vis[u] = true;
        for (int i = head[u]; ~i; i = G[i].next) {
            int v = G[i].to;
            if (vis[v] || (i & 1)) {
                continue;
            }
            DFS(v);
        }
        vs.pb(u);
    }
    void RDFS(int u, int k) {
        col[u] = k;
        vis[u] = true;
        for (int i = head[u]; ~i; i = G[i].next) {
            int v = G[i].to;
            if (vis[v] || !(i & 1)) {
                continue;
            }
            RDFS(v, k);
        }
    }
    int scc() {
        mem(vis, false);
        vs.clear();
        for (int i = 1; i <= n; ++i) {
            if (!vis[i]) {
                DFS(i);
            }
        }
        int k = 0;
        mem(vis, false);
        for (int i = vs.size() - 1; i >= 0; --i) {
            if (!vis[vs[i]]) {
                RDFS(vs[i], ++k);
            }
        }
        mem(in, 0);
        mem(out, 0);
        for (int u = 1; u <= n; ++u) {
            for (int i = head[u]; ~i; i = G[i].next) {
                int v = G[i].to;
                if (i & 1) {
                    continue;
                }
                if (col[u] != col[v]) {
                    out[col[u]]++;
                    in[col[v]]++;
                }
            }
        }
        return k;
    }
};
void Solve() {
    int k = _scc.scc();
    int zeroIn = 0;
    int zeroOut = 0;
    for (int i = 1; i <= k; ++i) {
        if (_scc.in[i] == 0) {
            zeroIn++;
        }
        if (_scc.out[i] == 0) {
            zeroOut++;
        }
    }
    printf("%d\n", zeroIn);
    if (k == 1) {
        printf("0\n");
    } else {
        printf("%d\n", max(zeroIn, zeroOut));
    }
}
void Init() {
    num = 0;
    mem(head, -1);
}
int main() {
    while (~scanf("%d", &n)) {
        Init();
        for (int i = 1; i <= n; ++i) {
            int v;
            while (scanf("%d", &v) && v) {
                addEdge(i, v);
                addEdge(v, i);
            }
        }
        Solve();
    }
    return 0;
}