Scribd
Upload
11 views2 pages

Code 5

The document contains a C++ implementation of a solution to find articulation points in a graph using Depth First Search (DFS). It defines a class 'Solution' with a method 'articulationPoints' that identifies nodes whose removal increases the number of connected components. The main function demonstrates the usage of this method with a sample graph.

Uploaded by

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

Code 5

The document contains a C++ implementation of a solution to find articulation points in a graph using Depth First Search (DFS). It defines a class 'Solution' with a method 'articulationPoints' that identifies nodes whose removal increases the number of connected components. The main function demonstrates the usage of this method with a sample graph.

Uploaded by

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

#include <bits/stdc++.

h>
using namespace std;

// User function Template for C++


class Solution {
private:
int timer = 1; // global timer for discovery time

// DFS function to detect articulation points


void dfs(int node, int parent, vector<int> &vis, int tin[], int low[],
vector<int> &mark, vector<int> adj[]) {

vis[node] = 1; // mark node as visited


tin[node] = low[node] = timer; // set discovery and low time
timer++; // increment timer
int child = 0; // count of children in DFS tree

for (auto it : adj[node]) {


if (it == parent) continue; // skip the edge to parent

if (!vis[it]) {
// If child not visited, explore it
dfs(it, node, vis, tin, low, mark, adj);

// Update the low time after visiting child


low[node] = min(low[node], low[it]);

// Articulation point condition for non-root


if (low[it] >= tin[node] && parent != -1) {
mark[node] = 1;
}

child++; // count number of DFS children


}
else {
// If already visited and not parent, it's a back edge
low[node] = min(low[node], tin[it]);
}
}

// Articulation point condition for root node


if (parent == -1 && child > 1) {
mark[node] = 1;
}
}

public:
// Main function to find all articulation points
vector<int> articulationPoints(int n, vector<int> adj[]) {
vector<int> vis(n, 0); // visited array
int tin[n]; // discovery time of each node
int low[n]; // lowest discovery time reachable
vector<int> mark(n, 0); // mark articulation points

// In case of disconnected components, run DFS from each node


for (int i = 0; i < n; i++) {
if (!vis[i]) {
dfs(i, -1, vis, tin, low, mark, adj);
}
}

// Collect all articulation points


vector<int> ans;
for (int i = 0; i < n; i++) {
if (mark[i] == 1) {
ans.push_back(i);
}
}

// If no articulation points found, return -1


if (ans.empty()) return {-1};
return ans;
}
};

int main() {
int n = 5;

// List of undirected edges


vector<vector<int>> edges = {
{0, 1}, {1, 4},
{2, 4}, {2, 3}, {3, 4}
};

// Build adjacency list


vector<int> adj[n];
for (auto it : edges) {
int u = it[0], v = it[1];
adj[u].push_back(v);
adj[v].push_back(u);
}

Solution obj;
vector<int> nodes = obj.articulationPoints(n, adj);

// Print articulation points


for (auto node : nodes) {
cout << node << " ";
}
cout << endl;

return 0;
}

You might also like