Some update s

update on 2021/8/12: Analysis on the advantages of Kosaraju algorithm is added.

1. Preface

Strongly connected components are something of graph theory.

This thing can turn a directed graph into a DAG, and various techniques can be used on DAG.

2. Definitions

Definition of component: in a given directed graph, if the points \ (a,b \) can reach each other, it is called that the points \ (a,b \) are in a component.

Obviously, the component is transitive, that is, if \ (a,b \) is in a component and \ (b,c \) is in a component, then \ (a,c \) is also in a component.

Strongly connected component: for a graph \ (G \), let its point set be \ (V \). If some points can be selected to form a point set \ (V '\), if all points in \ (V' \) are within one component, and all points in \ (V '\) are not within one component with points other than \ (V' \), then point \ (V '\) is called a strongly connected component of graph \ (G \).

According to the definition, all points in the strongly connected component can reach each other.

3. Seeking method

There are many methods to calculate the strong connected component, and the method used by the author is Kosaraju algorithm, which uses twice dfs to determine the strong connected component, that is, twice dfs to calculate the strong connected component.

The steps of the algorithm are as follows:

• First, do dfs for the whole graph (any point can be started). For each point, press the point into a stack \ (sta \) after traversing all its edges.
• Then reverse \ (sta \).
• Starting from the first element of \ (sta \), establish a reverse graph and do dfs in the reverse graph. At this time, all points that can be traversed from one point belong to a strongly connected component.

Note that the third step is sequential, that is, after reversing \ (sta \), select points to traverse from scratch, and each point is traversed only once.

So why is this algorithm correct?

Suppose \ (sta=\{a,b,c,...,z \} \) before inversion.

Then \ (z \) is the first one after inversion. Suppose \ (z \) can reach \ (a,b,c \) in the reverse graph.

So obviously, in the forward graph, it can be guaranteed that \ (a,b,c \) can reach \ (z \).

But why can \ (z \) reach \ (a,b,c \)?

Because in the \ (sta \) before inversion, \ (a,b,c \) precedes \ (z \).

This means that \ (a,b,c \) must be stacked before \ (z \), and before \ (z \), or \ (a,b,c \) is disconnected from \ (z \), but this situation has been ruled out.

Therefore, only when \ (z \) can reach \ (a,b,c \), can it indicate that \ (a,b,c \) precedes \ (z \).

The certificate is completed.

For the code of this part, you can see the shrinking point code of the application, which contains the code of strongly connected components.

In addition to Kosaraju algorithm, the most commonly used algorithm for finding strongly connected components is Tarjan algorithm.

So what are the advantages of Kosaraju algorithm?

• The idea is simpler and easier to understand than Tarjan algorithm.
• The code is not error prone.
• There is a magical feature that will be explained in the application section.

In particular, because the Tarjan algorithm for finding strongly connected components and the Tarjan algorithm for finding cut points and bridges are different in implementation details, sometimes it is easy to confuse the two, so the author only talks about Kosaraju algorithm.

4. Application

There are two applications of strongly connected components, one is contraction point and the other is 2 - SAT. here we only talk about contraction point.

Example: P3387 [template] shrinking point

One advantage of strongly connected components is the ability to turn a directed graph into a DAG.

• How?

Because all points in a strongly connected component can reach each other, we can combine the information of these points into one point, and then after doing so, the graph will become a DAG.

• Why DAG?

Suppose there are rings in the graph, then these points belong to a strongly connected component, but we have reduced all the strongly connected components to one point, which is a contradiction.

• What's the use of shrinking?

The best place to use DAG is topological sorting! Many graph problems can be solved by using topological sorting + DP.

code:

/*
========= Plozia =========
    Author:Plozia
    Problem:P3387 [Shrink point
    Date:2021/4/15
========= Plozia =========
*/

#include <bits/stdc++.h>
using std::queue;

typedef long long LL;
const int MAXN = 1e4 + 10, MAXM = 1e5 + 10;
int n, m, val[MAXN], cnt_EEdge = 1, a[MAXN], HHead[MAXN], cnt_Edge = 1, sta[MAXN], Top, col, Color[MAXN], Head[MAXN];
int cnt[MAXN], ans, f[MAXN];
struct node { int to, val, Next; } EEdge[MAXM << 1], Edge[MAXM << 1];
bool vis[MAXN];

int read()
{
    int sum = 0, fh = 1; char ch = getchar();
    for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
    for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
    return sum * fh;
}
void add_EEdge(int x, int y, int z) { ++cnt_EEdge; EEdge[cnt_EEdge] = (node){y, z, HHead[x]}; HHead[x] = cnt_EEdge; }
void add_Edge(int x, int y, int z) { ++cnt_Edge; Edge[cnt_Edge] = (node){y, z, Head[x]}; Head[x] = cnt_Edge; }
//Be careful not to mistake the storage of original and new pictures!!!
int Min(int fir, int sec) { return (fir < sec) ? fir : sec; }
int Max(int fir, int sec) { return (fir > sec) ? fir : sec; }

void dfs1(int now)
{
    vis[now] = 1;
    for (int i = HHead[now]; i; i = EEdge[i].Next)
    {
        int u = EEdge[i].to;
        if (EEdge[i].val == 0) continue;
        if (vis[u]) continue; dfs1(u);
    }
    sta[++Top] = now;//Enter the stack
}

void dfs2(int now, int col)
{
    vis[now] = 1; Color[now] = col;//Coloring, which strongly connected component is the record
    for (int i = HHead[now]; i; i = EEdge[i].Next)
    {
        int u = EEdge[i].to;
        if (vis[u] || EEdge[i].val == 1) continue;
        dfs2(u, col);
    }
}

void Topsort()//Topology sorting + DP
{
    queue <int> q;
    for (int i = 1; i <= col; ++i)
        if (cnt[i] == 0) q.push(i), ans = Max(ans, f[i] = a[i]);
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        for (int i = Head[x]; i; i = Edge[i].Next)
        {
            int u = Edge[i].to; --cnt[u];
            f[u] = Max(f[u], f[x] + a[u]);
            ans = Max(ans, f[u]);
            if (cnt[u] == 0) q.push(u);
        }
    }
}

int main()
{
    n = read(), m = read();
    for (int i = 1; i <= n; ++i) val[i] = read();
    for (int i = 1; i <= m; ++i)
    {
        int u = read(), v = read();
        add_EEdge(u, v, 1); add_EEdge(v, u, 0);
    }
    for (int i = 1; i <= n; ++i)
        if (!vis[i]) dfs1(i);//Primary dfs
    memset(vis, 0, sizeof(vis));
    std::reverse(sta + 1, sta + Top + 1);//Pay attention to reverse!
    for (int i = 1; i <= n; ++i)
        if (!vis[sta[i]]) { ++col; dfs2(sta[i], col); }//Quadratic dfs
    for (int i = 1; i <= cnt_EEdge; i += 2)
    {
        int u = EEdge[i ^ 1].to, v = EEdge[i].to;
        if (Color[u] != Color[v]) { add_Edge(Color[u], Color[v], 1); cnt[Color[v]]++; }
        //Create new map
    }
    for (int i = 1; i <= n; ++i) a[Color[i]] += val[i];//Handle point weights for new graphs
    Topsort(); printf("%d\n", ans);
    return 0;
}

Next, after confirming to understand the above code, explain the characteristics of Kosaraju algorithm:

• For the two points \ (i,j \) on the graph after the shrinking point, if \ (color_i < color_j \), then \ (I \) must be able to go to \ (J \). In other words, after finding the topological order of this graph \ (I \) is in front of \ (J \).

Why is there such a feature? The brief proof is as follows:

Consider three points first:

Let a, B and C in the figure above be three strongly connected components.

Consider the order of a, B and C in the stack when we first dfs.

Assuming that dfs starts from A first, then \ (A \to B \to C \), c enters the stack, B enters the stack, A enters the stack, CBA is in the stack, and ABC is after turning. When taking it out for the second pass of dfs \ (color_A < color_b < color_c \), the conclusion is tenable.

If you start dfs from B, then \ (B \to C \), C goes into the stack, B goes into the stack, and then start dfs from A again, A goes into the stack, the stack is also CBA, and after turning, it is also ABC.

At this point, you will find that the above paragraph illustrates two things:

• The correctness of the conclusion.
• Conclusion for any kind of dfs, the sequence is valid.

Combining these two points, we can know that the conclusion is completely correct when there are only three strongly connected components.

Now, when we generalize to the general case, for the graph built after we shrink the point, it is a DAG, and there are several chains on this DAG. For all the strongly connected components on each chain, we can learn by analogy with the proof of the above three points: no matter what order passes through the chain, the relative order of these strongly connected components in the flip stack is always sorted according to the relative order of these strongly connected components on the chain.

Since DAG is composed of common nodes of these chains, each chain meets the above properties, and naturally the whole DAG meets the above properties.

To sum up, the conclusion to be proved is tenable.

The above conclusions need to be used to find a set of feasible solutions for the 2 - SAT problem.

For those interested in the 2 - SAT question, please see my article: Graph theory topics - learning notes: 2 - SAT questions

5. Summary

Definition of strongly connected component: for a graph \ (G \), let its point set be \ (V \). If some points can be selected to form a point set \ (V '\), if all points in \ (V' \) are within one component, and all points in \ (V '\) are not within one component with points other than \ (V' \), then point \ (V '\) is called a strongly connected component of graph \ (G \).

Solution: Kosaraju algorithm adopts dfs twice, the first time is the forward graph, and the second time is the reverse graph after reversing the stack.

Application: shrink point and 2-SAT.