bedjovski's blog

By bedjovski, 12 years ago, In English

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

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Even though you fixed the problem, I want to advise you to take variable "sos" global. It's speed up your execution time.