Skip to content

Instantly share code, notes, and snippets.

@anshumanc007
Last active January 7, 2019 06:58
Show Gist options
  • Save anshumanc007/4618526e24aed7e8c7fa43405615c609 to your computer and use it in GitHub Desktop.
Save anshumanc007/4618526e24aed7e8c7fa43405615c609 to your computer and use it in GitHub Desktop.
/*articulation points by anshumanc007*/
//ANSHUMANC007
//ANSHUMANC007
#include <bits/stdc++.h>
#include<queue>
#include<stack>
#include<set>
#include<iterator>
using namespace std;
#define MAX 10000
bool visited[MAX];
long long int parent[MAX];
long long int low[MAX];
long long int ex[MAX];
long long int timer;
long long int root=0;
bool isarti[MAX];
void initialise()
{
long long int i;
for(i=0;i<MAX;i++)
{
visited[i]=false;
isarti[i]=false;
low[i]=100000000;
ex[i]=1000000000;
parent[i]=i;
timer=0;
}
}
void dfs(vector<long long int>adj[],long long int i)
{ timer++;
long long int j,child;
child=0;
visited[i]=true;
ex[i]=timer;
low[i]=timer;
for(auto j:adj[i])
{
if(!visited[j])
{
parent[j]=i;
child++;
dfs(adj,j);
low[i]=min(low[j],low[i]);
if(root==i && child>1)
{
isarti[i]=true;
//cout<<i<<endl;
}
if(root!=i && low[j]>=ex[i])
{
isarti[i]=true;
}
}
else if(parent[i]!=j)
{
low[i]=min(low[i],ex[j]);
}
}
}
//for edges
void dfs(vector<long long int>adj[],long long int i)
{ timer++;
long long int j,child;
child=0;
visited[i]=true;
ex[i]=timer;
low[i]=timer;
for(auto j:adj[i])
{
if(!visited[j])
{
parent[j]=i;
child++;
dfs(adj,j);
low[i]=min(low[j],low[i]);
if(low[j]>ex[i])
{
isarti[i]=true;
if(A[i][j]!=1)
{
A[i][j]=1;
A[j][i]=1;
coo++;
}
}
}
else if(parent[i]!=j)
{
low[i]=min(low[i],ex[j]);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment