[go: up one dir, main page]
Scribd
Upload
17 views3 pages

Tarjan Code

The document contains a C++ implementation of an algorithm to find Strongly Connected Components (SCCs) in a directed graph using Depth-First Search (DFS). It defines global variables for adjacency lists, discovery times, and other necessary data structures, and includes functions for initializing the graph, performing DFS, and counting SCCs. The main function reads the number of vertices and edges, initializes the graph, and outputs the number of SCCs found.

Uploaded by

minhdatlhp
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
17 views3 pages

Tarjan Code

The document contains a C++ implementation of an algorithm to find Strongly Connected Components (SCCs) in a directed graph using Depth-First Search (DFS). It defines global variables for adjacency lists, discovery times, and other necessary data structures, and includes functions for initializing the graph, performing DFS, and counting SCCs. The main function reads the number of vertices and edges, initializes the graph, and outputs the number of SCCs found.

Uploaded by

minhdatlhp
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

#include <iostream>

#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

// Global variables
vector<int> adj[1000005]; // Adjacency list as array of vectors
int ids[1000005]; // Discovery times array
int low[1000005]; // Lowest reachable vertex id array
bool onStack[1000005]; // Tracks vertices in current SCC array
stack<int> st; // Stack for DFS
int id = 0; // Current discovery time
int sccCount = 0; // Count of SCCs
int n; // Number of vertices

void dfs(int at) {


ids[at] = low[at] = id++;
st.push(at);
onStack[at] = true;

// Visit all neighbors


for (int to : adj[at]) {
if (ids[to] == -1) {
dfs(to);
low[at] = min(low[at], low[to]);
}
else if (onStack[to])
low[at] = min(low[at], ids[to]);
}

// Found an SCC
if (ids[at] == low[at]) {
while (!st.empty()) {
int node = st.top();
st.pop();
onStack[node] = false;
low[node] = ids[at];
if (node == at) break;
}
sccCount++;
}
}

int findSCC() {
for (int i = 0; i < n; i++)
if (ids[i] == -1)
dfs(i);
return sccCount;
}

void initialize(int vertices) {


n = vertices;
for (int i = 0; i < n; i++) {
adj[i].clear();
ids[i] = -1;
low[i] = 0;
onStack[i] = false;
}
id = 0 = sccCount = 0;
while (!st.empty()) st.pop(); // Clear stack
}
int main() {
int m; // Number of edges
cin >> n >> m; // Input number of vertices and edges

initialize(n);

// Input m edges
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
// Assuming 0-based indexing
adj[u].push_back(v);
}

int result = findSCC();


cout << "Number of Strongly Connected Components: " <<
result << endl;

return 0;
}

You might also like