### bedjovski's blog

By bedjovski, 9 years ago,

I have a problem calculating articulation points. I am following this document: http://www.gateguru.org/algorithms/biconnected_components.pdf

and here is my code

#include<cctype>
#include<cmath>
#include<string>
#include<list>
#include<deque>
#include<stack>
#include<utility>
#include<sstream>
#include<bitset>
#include<vector>
#include<algorithm>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<set>
#include<iostream>
#include<stdio.h>
#include<fstream>
using namespace std;

#define mp make_pair
#define pb push_back
#define ms(x,y) memset((x),(y),sizeof((x)))
#define all(c) c.begin(),c.end()
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define per(i,n) for(int i=n;i>=0;i--)
#define PER(i,a,n) for(int i=n;i>=a;i++)
#define REP(i,a,n) for(int i=a;i<n;i++)
#define IMA(v,x) ((v).find(x) != (v).end())
#define sz size()
#define F first
#define S second
#define uni(v) { \
sort(all(v)); \
(v).erase(unique((v).begin(), (v).end()), (v).end()); \
}

#define PI 3.141592653589793
#define EPS 0.000001
#define MOD 1000000007
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<string> VS;
int ans;
int rano[3005],d[3005],t;
bool e[3005];
void dfs(int u,VI sos[])
{
d[u]=t++;
rano[u]=d[u];
rep(i,sos[u].sz)
{
int w=sos[u][i];
if(d[w]==-1)
{
dfs(w,sos);
rano[u]=min(rano[u],rano[w]);
if(d[u]<=rano[u])
{
if(!e[u])
ans++;
e[u]=true;
}
}
else
rano[u]=min(rano[u],rano[w]);
}

}
int main()
{
VI sos[3005];
int n,m;
scanf("%d %d",&n,&m);
rep(i,m)
{
int x,y;
scanf("%d %d",&x,&y);
sos[x].pb(y);
sos[y].pb(x);
}
ms(rano,-1);
ms(d,-1);
ms(e,false);
int start=0;
t=0;
ans=0;
dfs(start,sos);
printf("%d\n",ans);
return 0;
}



Any idea how to fix it?

=================================

nevermind i have fixed it

• -3

By bedjovski, 9 years ago,

Are the contestants here divided into 2 divisions or everyone can participate in both division contests?