# Tarjan算法查找强联通组件的程序

2/10/2017来源：ASP.NET技巧人气：1927

tarjan算法是由Robert Tarjan提出的求解有向图强连通分量的线性时间的算法。

C++程序：

```// A C++ PRogram to find strongly connected components in a given
// directed graph using Tarjan's algorithm (single DFS)
#include<iostream>
#include <list>
#include <stack>
#define NIL -1
using namespace std;

// A class that represents an directed graph
class Graph
{
int V;    // No. of vertices

// A Recursive DFS based function used by SCC()
void SCCUtil(int u, int disc[], int low[],
stack<int> *st, bool stackMember[]);
public:
Graph(int V);   // Constructor
void addEdge(int v, int w);   // function to add an edge to graph
void SCC();    // prints strongly connected components
};

Graph::Graph(int V)
{
this->V = V;
}

{
}

// A recursive function that finds and prints strongly connected
// components using DFS traversal
// u --> The vertex to be visited next
// disc[] --> Stores discovery times of visited vertices
// low[] -- >> earliest visited vertex (the vertex with minimum
//             discovery time) that can be reached from subtree
//             rooted with current vertex
// *st -- >> To store all the connected ancestors (could be part
//           of SCC)
// stackMember[] --> bit/index array for faster check whether
//                  a node is in stack
void Graph::SCCUtil(int u, int disc[], int low[], stack<int> *st,
bool stackMember[])
{
// A static variable is used for simplicity, we can avoid use
// of static variable by passing a pointer.
static int time = 0;

// Initialize discovery time and low value
disc[u] = low[u] = ++time;
st->push(u);
stackMember[u] = true;

// Go through all vertices adjacent to this
list<int>::iterator i;
{
int v = *i;  // v is current adjacent of 'u'

// If v is not visited yet, then recur for it
if (disc[v] == -1)
{
SCCUtil(v, disc, low, st, stackMember);

// Check if the subtree rooted with 'v' has a
// connection to one of the ancestors of 'u'
// Case 1 (per above discussion on Disc and Low value)
low[u]  = min(low[u], low[v]);
}

// Update low value of 'u' only of 'v' is still in stack
// (i.e. it's a back edge, not cross edge).
// Case 2 (per above discussion on Disc and Low value)
else if (stackMember[v] == true)
low[u]  = min(low[u], disc[v]);
}

// head node found, pop the stack and print an SCC
int w = 0;  // To store stack extracted vertices
if (low[u] == disc[u])
{
while (st->top() != u)
{
w = (int) st->top();
cout << w << " ";
stackMember[w] = false;
st->pop();
}
w = (int) st->top();
cout << w << "\n";
stackMember[w] = false;
st->pop();
}
}

// The function to do DFS traversal. It uses SCCUtil()
void Graph::SCC()
{
int *disc = new int[V];
int *low = new int[V];
bool *stackMember = new bool[V];
stack<int> *st = new stack<int>();

// Initialize disc and low, and stackMember arrays
for (int i = 0; i < V; i++)
{
disc[i] = NIL;
low[i] = NIL;
stackMember[i] = false;
}

// Call the recursive helper function to find strongly
// connected components in DFS tree with vertex 'i'
for (int i = 0; i < V; i++)
if (disc[i] == NIL)
SCCUtil(i, disc, low, st, stackMember);
}

// Driver program to test above function
int main()
{
cout << "\nSCCs in first graph \n";
Graph g1(5);
g1.SCC();

cout << "\nSCCs in second graph \n";
Graph g2(4);
g2.SCC();

cout << "\nSCCs in third graph \n";
Graph g3(7);
g3.SCC();

cout << "\nSCCs in fourth graph \n";
Graph g4(11);
g4.SCC();

cout << "\nSCCs in fifth graph \n";
Graph g5(5);
g5.SCC();

return 0;
}

SCCs in first graph
4
3
1 2 0

SCCs in second graph
3
2
1
0

SCCs in third graph
5
3
4
6
2 1 0

SCCs in fourth graph
8 9
7
5 4 6
3 2 1 0
10

SCCs in fifth graph
4 3 2 1 0
Python程序：

# Python program to find strongly connected components in a given
# directed graph using Tarjan's algorithm (single DFS)
#Complexity : O(V+E)

from collections import defaultdict

#This class represents an directed graph
class Graph:

def __init__(self,vertices):
#No. of vertices
self.V= vertices

# default dictionary to store graph
self.graph = defaultdict(list)

self.Time = 0

# function to add an edge to graph
self.graph[u].append(v)

'''A recursive function that find finds and prints strongly connected
components using DFS traversal
u --> The vertex to be visited next
disc[] --> Stores discovery times of visited vertices
low[] -- >> earliest visited vertex (the vertex with minimum
discovery time) that can be reached from subtree
rooted with current vertex
st -- >> To store all the connected ancestors (could be part
of SCC)
stackMember[] --> bit/index array for faster check whether
a node is in stack
'''
def SCCUtil(self,u, low, disc, stackMember, st):

# Initialize discovery time and low value
disc[u] = self.Time
low[u] = self.Time
self.Time += 1
stackMember[u] = True
st.append(u)

# Go through all vertices adjacent to this
for v in self.graph[u]:

# If v is not visited yet, then recur for it
if disc[v] == -1 :

self.SCCUtil(v, low, disc, stackMember, st)

# Check if the subtree rooted with v has a connection to
# one of the ancestors of u
# Case 1 (per above discussion on Disc and Low value)
low[u] = min(low[u], low[v])

elif stackMember[v] == True:

'''Update low value of 'u' only if 'v' is still in stack
(i.e. it's a back edge, not cross edge).
Case 2 (per above discussion on Disc and Low value) '''
low[u] = min(low[u], disc[v])

# head node found, pop the stack and print an SCC
w = -1 #To store stack extracted vertices
if low[u] == disc[u]:
while w != u:
w = st.pop()
print w,
stackMember[w] = False

print""

#The function to do DFS traversal.
# It uses recursive SCCUtil()
def SCC(self):

# Mark all the vertices as not visited
# and Initialize parent and visited,
# and ap(articulation point) arrays
disc = [-1] * (self.V)
low = [-1] * (self.V)
stackMember = [False] * (self.V)
st =[]

# Call the recursive helper function
# to find articulation points
# in DFS tree rooted with vertex 'i'
for i in range(self.V):
if disc[i] == -1:
self.SCCUtil(i, low, disc, stackMember, st)

# Create a graph given in the above diagram
g1 = Graph(5)
print "SSC in first graph "
g1.SCC()

g2 = Graph(4)
print "\nSSC in second graph "
g2.SCC()

g3 = Graph(7)
print "\nSSC in third graph "
g3.SCC()

g4 = Graph(11)
print "\nSSC in fourth graph "
g4.SCC();

g5 = Graph (5)
print "\nSSC in fifth graph "
g5.SCC();

#This code is contributed by Neelam Yadav