Definiation : What is SCC?

"SCC" means "strongly connected components.

In a directed graph , the nodes in the same SCC can visit each other.

In an easy way of understanding, if node $$$x$$$ and node $$$y$$$ are in the same SCC, there is a path from $$$x$$$ to $$$y$$$ and a path from $$$y$$$ to $$$x$$$.

For example, in this graph, nodes in same color are in the same SCC:

How to solve? Tarjan!

This problem is the templet of SCC. After you read this aritical, you can go and solve it.

Tarjan is one of the algorithms which can solve this problems.

First I am going to introduce two arrays to you:

• $$$low_x$$$: An array of trace values representing the minimum idx of points on a search tree rooted at $$$x$$$ which can be reached by only one edge which is not in the search tree.

• $$$dfn_x$$$: Timestamp array, representing the order it was visited.

For example we can get the two values of the nodes:

How to calculate $$$low_x$$$?

We assume that there is an undirected edge from the node $$$x$$$ to the node $$$y$$$. There are two conditions:

• First: If node $$$y$$$ is a node of the subtree of node $$$x$$$, so low[x] = min(low[x], low[y]);
• Secound: Else low[x] = min(low[x], dfn[y]);

Node that: In the secound condition, it is $$$dfn_y$$$, and it isn't $$$low_y$$$.

We should look back to the defination:

by only one edge which is not in the search tree

Only one edge!

How to find SCC base on $$$low$$$ and $$$dfn$$$?

Lets look back to the sample:

We can find that in each SCC there is a "head" which $$$low_x = dfn_x$$$. In this graph, the "heads" are node $$$1$$$ and node $$$3$$$.

We can use a stack to put the nodes we visited. When we get a "head", we should pop the elements in the stack and put them in the same SCC.

Lets read the sample together:

In this way, we can find the SCCs.

code in c++

void tarjan(int node)
{
	printf("%d ", node);
	stack[top++] = node;
	low[node] = dfn[node] = ++id;
	for (int i = head[node]; i; i = e[i].nxt)
	{
		int to = e[i].to;
		if (dfn[to] == 0)
		{
			tarjan(to);
			low[node] = min(low[node], low[to]);
		}
		else if (scc[to] == 0)
			low[node] = min(low[node], dfn[to]);
	}
	if (low[node] == dfn[node])
	{
		++color_cnt;
		ans.push_back(vector <int>());
		while (true)
		{
			int to = stack[--top];
			ans[color_cnt-1].push_back(to);
			scc[to] = color_cnt;
			if (node == to) break;
		}
	}
}

Recommend : More about connected components

If you want to learn more about connected components, can can read this aritical : A brief introduction of Tarjan and E-DCC（EBC).