强连通分量的题目列表（一）

强连通的概念：有向图，其中每个点都相互可达。

强连通有两个算法，Kosaraju算法和tarjan算法， 但是tarjan算法更快，一般用这个。

题目列表：

①基础题 LA 4287    和POJ3352 边双连通 最后的ans的判断方法做一下区别 双连通（一）

②强连通+dp UVA11324（二）

③强连通+数学 cf 711 div2 D（三）

④强连通+缩点 HDU 3836 （四）

一：等价性证明 LA 4287 蓝书 322

思路：强连通分量取出来以后看成一个点，于是就是一个DAG，然后让DAG最后变成强连通即可。然后要满足每个点的入度和出度都存在，这样才能表达等价。ans=max(入度不存在的个数，出度不存在的个数)

注意一个trick，如果本来就是强连通了，ans就是0

//看看会不会爆int! 或者绝对值问题。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define all(a) a.begin(), a.end()
const int maxn = 20000 + 5;
vector<int> G[maxn];
int pre[maxn], low[maxn], c[maxn];
int n, m;
stack<int> s;
int dfstime, scc_cnt;

void dfs(int u, int fa){
    pre[u] = low[u] = ++dfstime;
    int len = G[u].size();
    s.push(u);
    for (int i = 0; i < len; i++){
        int v = G[u][i];
        if (pre[v] == -1){
            dfs(v, u);
            low[u] = min(low[u], low[v]);
        }
        /*else if (low[v] < pre[u] && v != fa){///双连通里面，这里是通过反向边更新的
            low[u] = min(low[u], low[v]);
        }*/
        else if (!c[v]){///下面为什么是pre[v]而不是low[v](两者都可以)
            low[u] = min(low[u], pre[v]);///因为环装最后总会变回来，一样的
        }
    }
    if (low[u] == pre[u]){
        scc_cnt++;
        while (true){
            int x = s.top(); s.pop();
            c[x] = scc_cnt;
            if (x == u) break;
        }
    }
    return ;
}
int in[maxn], ou[maxn];
int main(){
    int t; cin >> t;
    while (t--){
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) G[i].clear();
        for (int i = 1; i <= m; i++){
            int u, v; scanf("%d%d", &u, &v);
            G[u].pb(v);
        }
        memset(c, 0, sizeof(c));
        memset(pre, -1, sizeof(pre));
        memset(low, 0, sizeof(low));
        dfstime = scc_cnt = 0;
        for (int i = 1; i <= n; i++){
            if (pre[i] == -1){
                dfs(i, -1);
            }
        }
        memset(in, 0, sizeof(in));
        memset(ou, 0, sizeof(ou));
        for (int i = 1; i <= n; i++){
            int len = G[i].size();
            for (int j = 0; j < len; j++){
                int v = G[i][j];
                if (c[i] != c[v]) {
                    in[c[i]]++;
                    ou[c[v]]++;
                }
            }
        }
        int ans1 = 0, ans2 = 0;
        for (int i = 1; i <= scc_cnt; i++){
            if (in[i] == 0) ans1++;
            if (ou[i] == 0) ans2++;
        }
        if (scc_cnt == 1) ans1 = ans2 = 0;
        //printf("scc_cnt = %d
", scc_cnt);
        printf("%d
", max(ans1, ans2));
    }
    return 0;
}
View Code

学习：注意dfs的else if条件，注意trick条件

二：最大团 UVA11324 蓝书323

题目大意：给一张有向图G，求一个结点数最大的节点集，是的该节点集中任意两个节点u和v，满足要么u可以到v，要么v可以到u或者两者可以相互可达。

思路：有向图，我们先求出强连通，然后让图变成一个DAG，然后在dp一下就行了。dp[i]表示从i出发的最长的距离

  1 //看看会不会爆int! 或者绝对值问题。
  2 #include <bits/stdc++.h>
  3 using namespace std;
  4 #define LL long long
  5 #define pb push_back
  6 #define mk make_pair
  7 #define fi first
  8 #define se second
  9 #define all(a) a.begin(), a.end()
 10 const int maxn = 1000 + 5;
 11 vector<int> G[maxn];
 12 int n, m, dfstime, scc_cnt;
 13 int pre[maxn], sccnu[maxn], low[maxn];
 14 stack<int> s;
 15 
 16 void dfs(int u){
 17     low[u] = pre[u] = ++dfstime;
 18     int len = G[u].size();
 19     s.push(u);
 20     for (int i = 0; i < len; i++){
 21         int v = G[u][i];
 22         if (pre[v] == -1){
 23             dfs(v);
 24             low[u] = min(low[u], low[v]);
 25         }
 26         else if (!sccnu[v]){
 27             low[u] = min(low[u], pre[v]);
 28         }
 29     }
 30     if (low[u] == pre[u]){
 31         //printf("u = %d
", u);
 32         scc_cnt++;
 33         while (true){
 34             int x = s.top(); s.pop();
 35             sccnu[x] = scc_cnt;
 36             if (x == u) break;
 37         }
 38     }
 39     return ;
 40 }
 41 int cnt[maxn], dp[maxn], vis[maxn];
 42 int a[maxn][maxn];
 43 
 44 int ans_dfs(int u){
 45     //printf("u = %d
", u);
 46     int &ans = dp[u];
 47     if (ans > 0) return ans;
 48     ans = cnt[u];
 49     for (int i = 1; i <= scc_cnt; i++){
 50         if (a[u][i] && i != u){
 51             //printf("u = %d i = %d
", u, i);
 52             //printf("dp[u] = %d
", dp[u]);
 53             ans = max(ans, ans_dfs(i) + cnt[u]);
 54             //printf("ans = %d, cnt[%d] = %d
", ans, i, cnt[i]);
 55         }
 56     }
 57     return ans;
 58 }
 59 
 60 
 61 int main(){
 62     int t; cin >> t;
 63     while (t--){
 64         scanf("%d%d", &n, &m);
 65         for (int i = 1; i <= n; i++){
 66             G[i].clear();
 67         }
 68         for (int i = 1; i <= m; i++){
 69             int u, v; scanf("%d%d", &u, &v);
 70             G[u].pb(v);
 71         }
 72         memset(pre, -1, sizeof(pre));
 73         memset(sccnu, 0, sizeof(sccnu));
 74         memset(low, 0, sizeof(low));
 75         dfstime = scc_cnt = 0;
 76         for (int i = 1; i <= n; i++){
 77             if (pre[i] == -1) dfs(i);
 78         }
 79         memset(cnt, 0, sizeof(cnt));
 80         memset(a, 0, sizeof(a));
 81         for (int i = 1; i <= n; i++){
 82             int x = sccnu[i];
 83             cnt[x]++;
 84             int len = G[i].size();
 85             for (int j = 0; j < len; j++){
 86                 int v = G[i][j];
 87                 int y = sccnu[v];
 88                 if (x == y) continue;
 89                 a[x][y] = 1;
 90                 //printf("%d %d
", x, y);
 91             }
 92         }
 93         memset(dp, 0, sizeof(dp));
 94         int ans = 0;
 95         for (int i = 1; i <= scc_cnt; i++) {
 96             ans_dfs(i);
 97         }
 98         for (int i = 1; i <= scc_cnt; i++) {
 99             //printf("dp[%d] = %d
", i, dp[i]);
100             ans = max(ans, dp[i]);
101         }
102 
103         printf("%d
", ans);
104     }
105     return 0;
106 }
View Code

三：codeforces 711 div2 D http://codeforces.com/contest/711/problem/D

题目大意：给你一个有向图，每个节点的出度都为1，定义confusing road为这个图中存在环，目前有一种操作：将一条路的方向翻转，翻转次数任意。问有几种翻转操作能让该图中不存在环。

思路：因为出度为1，所以只存在简单环，只需要用tarjan把所有环取出来，然后每次乘以2^x - 2即可，x表示环中的点数，减2表示该点数情况下形成的环的种类数只有两种。然后x=1的时候特判一下就行了。

//看看会不会爆int! 或者绝对值问题。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define all(a) a.begin(), a.end()
const int maxn = 200000 + 5;
vector<int> G[maxn];
int n, m, dfstime, scc_cnt;
int pre[maxn], sccnu[maxn], low[maxn];
stack<int> s;

void dfs(int u){
    low[u] = pre[u] = ++dfstime;
    int len = G[u].size();
    s.push(u);
    for (int i = 0; i < len; i++){
        int v = G[u][i];
        if (pre[v] == -1){
            dfs(v);
            low[u] = min(low[u], low[v]);
        }
        else if (!sccnu[v]){
            low[u] = min(low[u], pre[v]);
        }
    }
    if (low[u] == pre[u]){
        scc_cnt++;
        while (true){
            int x = s.top(); s.pop();
            sccnu[x] = scc_cnt;
            if (x == u) break;
        }
    }
    return ;
}

LL cnt[maxn];
const LL mod = 1e9 + 7;

LL cal(LL x, LL n){
    LL ans = 1;
    while (n){
        if (n & 1) ans = ans * x % mod;
        n >>= 1; x = x * x % mod;
    }
    return ans - 2;
}
int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        G[i].clear();
    }
    for (int i = 1; i <= n; i++){
        int v;
        scanf("%d", &v);
        G[i].pb(v);
    }
    memset(pre, -1, sizeof(pre));
    memset(sccnu, 0, sizeof(sccnu));
    memset(low, 0, sizeof(low));
    dfstime = scc_cnt = 0;
    for (int i = 1; i <= n; i++){
        if (pre[i] == -1) dfs(i);
    }
    for (int i = 1; i <= n; i++){
        cnt[sccnu[i]]++;
    }
    LL ans = 1;
    for (int i = 1; i <= scc_cnt; i++){
        if (cnt[i] == 1) ans = ans * 2 % mod;
        else {
            ans = ans * cal(2, cnt[i]) % mod;
        }
    }
    printf("%I64d
", ans);
    return 0;
}
View Code

四：HDU 3836

题目大意：将题目中的集合转换为顶点，A集合是B集合的子集，转换为一条有向边<A,B>，即题目给我们一个有向图，问最少需要添加多少条边使之成为强连通图。 

思路：强连通以后缩点，然后定义入度为in，出度为out，答案为max(in_cnt, out_cnt).

//看看会不会爆int!数组会不会少了一维！
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker,"/STACK:102400000,102400000")
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define haha printf("haha
")
const int maxn = 50000 + 5;
vector<int> G[maxn];
int pre[maxn], low[maxn], c[maxn];
int n, m;
stack<int> s;
int dfstime, scc_cnt;

void dfs(int u, int fa){
    pre[u] = low[u] = ++dfstime;
    int len = G[u].size();
    s.push(u);
    for (int i = 0; i < len; i++){
        int v = G[u][i];
        if (pre[v] == -1){
            dfs(v, u);
            low[u] = min(low[u], low[v]);
        }
        else if (!c[v]){///下面为什么是pre[v]而不是low[v](两者都可以)
            low[u] = min(low[u], pre[v]);///因为环装最后总会变回来，一样的
        }
    }
    if (low[u] == pre[u]){
        scc_cnt++;
        while (true){
            int x = s.top(); s.pop();
            c[x] = scc_cnt;
            if (x == u) break;
        }
    }
    return ;
}
int in[maxn], out[maxn];
void init(){
    for (int i = 1; i <= n; i++) G[i].clear();
    memset(in, 0, sizeof(in));
    memset(out, 0, sizeof(out));
    memset(pre, -1, sizeof(pre));
    memset(low, 0, sizeof(low));
    memset(c, 0, sizeof(c));
    while (!s.empty()) s.pop();
    dfstime = scc_cnt = 0;
}

int solve(){
    for (int i = 1; i <= m; i++){
        int u, v; scanf("%d%d", &u, &v);
        G[u].push_back(v);
    }
    for (int i = 1; i <= n; i++){
        if (pre[i] == -1) dfs(i, -1);
    }
    if (scc_cnt == 1) return 0;
    for (int i = 1; i <= n; i++){
        for (int j = 0; j < G[i].size(); j++){
            int v = G[i][j], u = i;
            if (c[v] != c[u]) out[c[u]]++, in[c[v]]++;
        }
    }
    int t1 = 0, t2 = 0;
    for (int i = 1; i <= scc_cnt; i++){
        if (out[i] == 0) t1++;
        if (in[i] == 0) t2++;
    }
    return max(t1, t2);
}

int main(){
    while (scanf("%d%d", &n, &m) != EOF){
        if (n == 1) {printf("0
"); continue;}
        init();
        printf("%d
", solve());
    }
    return 0;
}
View Code

关键：缩点

五：

六：

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/heimao5027/p/5815900.html