Cod sursa(job #703423)

Utilizator AplayLazar Laurentiu Aplay Data 2 martie 2012 12:21:26
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.08 kb
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
typedef struct nod{ int x; nod *urm;}NODE;
NODE *v[100010];
int n,m,d[100010],minn[100010],k;
stack <pair <int, int> > st;
vector <vector <int> > C;

int minimu(int a, int b)
{
    if(a<=b) return a;
    return b;
}

void citire()
{
    FILE *f=fopen("biconex.in","r");
    NODE*q;
    int x,y;
    fscanf(f,"%d%d",&n,&m);
    for(int i=0;i<m;++i)
    {
        fscanf(f,"%d%d",&x,&y);
        q=(NODE*)malloc(sizeof(NODE));
        q->x=y;
        q->urm = v[x];
        v[x] = q;
        q=(NODE*)malloc(sizeof(NODE));
        q->x=x;
        q->urm = v[y];
        v[y] = q;
    }
    fclose(f);
}

void fa(int x,int y)
{
    vector <int> tz;
    int xx, yy;
    do
    {
        xx = st.top().first;
        yy = st.top().second;
        st.pop();
        tz.push_back(xx);
        tz.push_back(yy);
    }while(xx!= x || yy != y);
    C.push_back(tz);
}

void dfs(int nod,int tata,int dist)
{
    d[nod]=minn[nod]=dist;
    int nrf=0;
    bool critic = false;
    NODE *q=v[nod];
    while(q)
    {
        if(q->x != tata)
            if(d[q->x]==-1)
            {
                ++nrf;
                st.push(make_pair(nod,q->x));
                dfs(q->x,nod,dist+1);
                minn[nod] = minimu(minn[q->x],minn[nod]);
                if(minn[q->x] >= d[nod])
                    fa(nod,q->x); //critic = true;

            }
        else
            minn[nod] = minimu(minn[nod],d[q->x]);
        q=q->urm;
    }
}

int main()
{
    citire();
    for(int i=1;i<=n;++i) d[i]=-1;
    dfs(1,0,0);
    FILE *f=fopen("biconex.out","w");
    fprintf(f,"%d\n",C.size());
    for(int i=0;i<C.size(); ++i)
    {
        sort(C[i].begin(),C[i].end());
        int aux=0,j=0;
        do
        {
            fprintf(f,"%d ",C[i][j]);
            for(; C[i][j] == C[i][aux] &&j<=C[i].size() ;++j);
            aux = j;
        }while(j<C[i].size());
        fprintf(f,"\n");
    }
    fclose(f);
    return 0;
}