#include <bits/stdc++.h>
using namespace std;
//User function Template for C++
class Solution {
private:
int timer = 1;
void dfs(int node, int parent, vector<int> &vis, int tin[], int low[],
vector<int> &mark, vector<int>adj[]) {
vis[node] = 1;
tin[node] = low[node] = timer;
timer++;
int child = 0;
for (auto it : adj[node]) {
if (it == parent) continue;
if (!vis[it]) {
dfs(it, node, vis, tin, low, mark, adj);
low[node] = min(low[node], low[it]);
if (low[it] >= tin[node] && parent != -1) {
mark[node] = 1;
}
child++;
}
else {
low[node] = min(low[node], tin[it]);
}
}
if (child > 1 && parent == -1) {
mark[node] = 1;
}
}
public:
vector<int> articulationPoints(int n, vector<int>adj[]) {
vector<int> vis(n, 0);
int tin[n];
int low[n];
vector<int> mark(n, 0);
for (int i = 0; i < n; i++) {
if (!vis[i]) {
dfs(i, -1, vis, tin, low, mark, adj);
}
}
vector<int> ans;
for (int i = 0; i < n; i++) {
if (mark[i] == 1) {
ans.push_back(i);
}
}
if (ans.size() == 0) return { -1};
return ans;
}
};
int main() {
int n = 5;
vector<vector<int>> edges = {
{0, 1}, {1, 4},
{2, 4}, {2, 3}, {3, 4}
};
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);
for (auto node : nodes) {
cout << node << " ";
}
cout << endl;
return 0;
}
Comments