• 1. • This is the code that I have studied for finding SCC and I have several doubts.

vi dfs_num, dfs_low, S, visited;

void tarjanSCC(int u) {

dfs_low[u] = dfs_num[u] = dfsNumberCounter++;

S.push_back(u);

visited[u] = 1;

for (int j = 0; j < (int)AdjList[u].size(); j++) {

ii v = AdjList[u][j];

if (dfs_num[v.first] == UNVISITED)

tarjanSCC(v.first);

if (visited[v.first]) // condition for update

dfs_low[u] = min(dfs_low[u], dfs_low[v.first]); }

if (dfs_low[u] == dfs_num[u]) {

printf("SCC %d:", ++numSCC);

while (1) {

int v = S.back(); S.pop_back(); visited[v] = 0; // why visited[v]=0 is done?

printf(" %d", v);

if (u == v) break; }

printf("\n");

} }

// inside int main()

dfs_num.assign(V, UNVISITED); dfs_low.assign(V, 0); visited.assign(V, 0);

dfsNumberCounter = numSCC = 0;

for (int i = 0; i < V; i++)

if (dfs_num[i] == UNVISITED)

tarjanSCC(i);

//code is from steven and felix book.

Can one node be contained in two SCCs?

5 6

1 4

1 3

2 4

3 4

4 5

5 1

consider this testcase — 5 is number of nodes and 6 is the number of directed edges. 1 4 means there is an directed edge from 1 to 4.

if I assume that one node is contained in only one SCC then 1->4->5 will be considered or 1->3->4->5 for 1, 4 and 5.

And how we update dfs_low[u] in case of visited node as dfs_low[u]=min(dfs_low[u], dfs_low[v.first]) or as dfs_low[u]=min(dfs_low[u], dfs_num[v.first]). Which one is correct and why ?

Any help would be appreciated.