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

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

阅读量：803 次

发布时间：2023-03-03

本文共 2830 字，大约阅读时间需要 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;}