2018-03-06

scc

scc模板

原理

求解强联通块的时候，运用两次dfs

第一次dfs的时候求出后序遍历的顺序。
第二次dfs的时候通过反向图，求出每一个连通块。

题目

poj 2186Popular Cows

题意

若A认为B是红牛，B认为C是红牛，那么A也认为C是红牛。这样具有传递的关系。
求出被所有的牛公认的红牛的个数。

题解

一个强联通块内，所有牛都相互认为是红牛。
有向图中，最后一个强联通块内的红牛被公认为红牛。因此只需要求最后一个强联通块内牛的只数就行了
最后注意判断是否有不连通的情况，即从最后一个块中的红牛出发，反向遍历整张图，看是否所有的点都可达。

AC 代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
/*
12 16
12 11
11 8
11 10
8 10
10 9
9 8
9 7
7 6
6 5
5 7
6 3
6 4
4 3
3 2
2 3
4 1
*/
using namespace std;
const int maxn = 1e4+10;
vector<int> G[maxn];
vector<int> rG[maxn];
bool vis[maxn];
int index[maxn];
vector<int> vs;
void add_edge(int u, int v){
    G[u].push_back(v);
    rG[v].push_back(u);
}
int n, m;
void dfs(int u){
    vis[u] = true;
    for(int i=0; i<G[u].size(); i++){
        if(!vis[G[u][i]]) dfs(G[u][i]);
    }
    vs.push_back(u);
}
void rdfs(int v, int k){
    vis[v] = true;
    index[v] = k;
    for(int i=0; i<rG[v].size(); i++){
        if(!vis[rG[v][i]])rdfs(rG[v][i], k);
    }
}
int scc(){
    memset(vis, 0, sizeof(vis));
    vs.clear();
    for(int i=0; i<n; i++){
        if(!vis[i]) dfs(i);
    }
    memset(vis, 0, sizeof(vis));
    int k = 0;
    for(int i=vs.size()-1; i>=0; i--){
        if(!vis[vs[i]]){
            rdfs(vs[i], k++);
        }
    }
    int u=-1;
    int ans = 0;
    for(int i=0; i<n; i++){
        if(index[i] == k-1){
            u = i;
            ans++;
        }
    }
    memset(vis, 0, sizeof(vis));
    rdfs(u, 0);
    for(int i=0; i<n; i++){
        if(!vis[i]){
            ans = 0;
            break;
        }
    }
    printf("%d\n", ans);
}
int main()
{
    while(~scanf("%d%d", &n, &m)){
        for(int i=0; i<n; i++){
            G[i].clear();
            rG[i].clear();
        }
        int u, v;
        for(int i=0; i<m; i++){
            scanf("%d%d", &u, &v);
            add_edge(u-1, v-1);
        }
        scc();
    }
    return 0;
}

tarjan算法来求有向图的强联通分量

时间复杂度是线性的，常数比前面的Kosaraju的算法小一点，所以更推荐这个算法

算法的思想和求割点有点像

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
int pre[maxn], low[maxn], sccno[maxn];
int dfs_clock, scc_cnt;
vector<int> G[maxn];
int n, m;
stack<int> S;
void dfs(int u){
    pre[u] = low[u] = ++dfs_clock;
    S.push(u);
    for(int i=0; i<G[u].size(); i++){
        int v = G[u][i];
        if(!pre[v]){
            dfs(v);
            low[u] = min(low[u], low[v]);
        }
        else if(!sccno[v]){
            low[u] = min(low[u], pre[v]);
        }
    }
    if(low[u] == pre[u]){
        ++scc_cnt;
        while(!S.empty()){
            int temp = S.top();
            S.pop();
            sccno[temp] = scc_cnt;
            if(temp == u) break;
        }
    }
}
void find_scc(){
    memset(pre, 0 ,sizeof(pre));
    memset(low, 0, sizeof(low));
    memset(sccno, 0, sizeof(sccno));
    dfs_clock = scc_cnt = 0;
    for(int i=0; i<n; i++){
        if(!pre[i]){
            dfs(i);
        }
    }
}
int main(){
    while(~scanf("%d%d", &n, &m)){
        for(int i=0; i<n; i++) G[i].clear();
        int u, v;
        for(int i=0; i<m; i++){
            scanf("%d%d", &u, &v);
            G[u-1].push_back(v-1);
        }
        find_scc();
        for(int i=0; i<n; i++){
            printf("%d ", sccno[i]);
        }
        printf("\n");
    }
    return 0;
}

未解决的问题

如何进行相应的缩点。
能进行释放点吗？
~~有时间学习一波tarjan的算法tarjan算法求有向图的强联通分量~~

本文标题:scc

文章作者:Babydragon

发布时间:2018-03-06, 09:13:10

最后更新:2018-03-23, 13:30:56

原始链接:http://baolintian.github.io/2018/03/06/scc/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。