2013-team5/SCC

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
/*
    SCC-Kosaraju
    O(n+m)
    By Kotomi
*/

#include <cstring>
#include <map>

using namespace std;

typedef pair<int, int> PII;

class SCC{
public:

    static const int maxV = 100010;
    static const int maxE = 100010;

    int vect[3][maxV];
    int vis[maxV];
    int tot[3];

    int low[maxV];
    int ord[maxV];
    int num[maxV];
    int col, cnt;

    int n, m;

    map<PII, int> hash;

    void add(int k, int u, int v)
    {
        tot[k]++;
        edge[k][tot[k]].v = v;
        edge[k][tot[k]].next = vect[k][u];
        vect[k][u] = tot[k];
    }

    struct graph
    {
        int v, next;
    }edge[3][maxE];    

    void init()
    {
    tot[0] = tot[1] = tot[2] = 0;
    memset(vect, 0, sizeof(vect));
        cnt = col = 0;
    }


    void dfs(int u)
    {
        vis[u] = 1;
        for (int tt = vect[0][u]; tt; tt = edge[0][tt].next){
            int v = edge[0][tt].v;
            if (!vis[v]) dfs(v);
        }
        ord[++cnt] = u;
    }

    void back(int u)
    {
        low[u] = col;
        num[col]++;
        for (int tt= vect[1][u]; tt; tt = edge[1][tt].next){
            int v = edge[1][tt].v;
            if (!low[v]) back(v);
        }
    }


    void kosaraju(){
        memset(vis, 0, sizeof(vis));
        for (int i = 1; i <= n; i++){
            if (!vis[i]) dfs(i);
        }

        memset(low, 0, sizeof(low));
        memset(num, 0, sizeof(num));
        for (int i = cnt; i > 0; i--){   
            if (!low[ord[i]]){
                col++;
                back(ord[i]);
            }
        }

        hash.clear();
        memset(vis, 0, sizeof(vis));
        for (int u = 1; u <= n; u++){
            for (int tt = vect[0][u]; tt; tt = edge[0][tt].next){
                int v = edge[0][tt].v;
                if (low[u] != low[v] && !hash.count(make_pair(low[u], low[v]))){
                    add(2, low[u], low[v]);
                    hash[make_pair(low[u], low[v])] = 1;
                    vis[low[v]] = 1;
                }
            }
        }
    }
};
}}}

/*
    SCC-Kosaraju
    O(n+m)
    By Kotomi
*/
#include <cstring>
#include <map>
using namespace std;
typedef pair<int, int> PII;
class SCC{
public:
    static const int maxV = 100010;
    static const int maxE = 100010;
    int vect[3][maxV];
    int vis[maxV];
    int tot[3];
    int low[maxV];
    int ord[maxV];
    int num[maxV];
    int col, cnt;
    int n, m;
    map<PII, int> hash;
    void add(int k, int u, int v)
    {
        tot[k]++;
        edge[k][tot[k]].v = v;
        edge[k][tot[k]].next = vect[k][u];
        vect[k][u] = tot[k];
    }
    struct graph
    {
        int v, next;
    }edge[3][maxE];    
    void init()
    {
    tot[0] = tot[1] = tot[2] = 0;
    memset(vect, 0, sizeof(vect));
        cnt = col = 0;
    }
    void dfs(int u)
    {
        vis[u] = 1;
        for (int tt = vect[0][u]; tt; tt = edge[0][tt].next){
            int v = edge[0][tt].v;
            if (!vis[v]) dfs(v);
        }
        ord[++cnt] = u;
    }
    void back(int u)
    {
        low[u] = col;
        num[col]++;
        for (int tt= vect[1][u]; tt; tt = edge[1][tt].next){
            int v = edge[1][tt].v;
            if (!low[v]) back(v);
        }
    }
    void kosaraju(){
        memset(vis, 0, sizeof(vis));
        for (int i = 1; i <= n; i++){
            if (!vis[i]) dfs(i);
        }
        memset(low, 0, sizeof(low));
        memset(num, 0, sizeof(num));
        for (int i = cnt; i > 0; i--){   
            if (!low[ord[i]]){
                col++;
                back(ord[i]);
            }
        }
        hash.clear();
        memset(vis, 0, sizeof(vis));
        for (int u = 1; u <= n; u++){
            for (int tt = vect[0][u]; tt; tt = edge[0][tt].next){
                int v = edge[0][tt].v;
                if (low[u] != low[v] && !hash.count(make_pair(low[u], low[v]))){
                    add(2, low[u], low[v]);
                    hash[make_pair(low[u], low[v])] = 1;
                    vis[low[v]] = 1;
                }
            }
        }
    }
};