Cod sursa(job #1168127)

Utilizator maritimCristian Lambru maritim Data 6 aprilie 2014 23:58:03
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

typedef vector<int>::iterator it;

FILE *f = fopen("biconex.in","r");
FILE *g = fopen("biconex.out","w");

#define MaxN 100100

int N,M,Sol,st;
int viz[MaxN],stiva[MaxN];
vector<int> A[MaxN];
vector<int> SolV[MaxN];

void citire(void)
{
    int a,b;

    fscanf(f,"%d %d",&N,&M);
    for(int i=1;i<=M;i++)
    {
        fscanf(f,"%d %d",&a,&b);
        A[a].push_back(b);
        A[b].push_back(a);
    }
}

inline void adaugaComp(int a,int poz)
{
    ++ Sol;

    SolV[Sol].push_back(a);

    for(;stiva[st+1]!=poz;--st)
        SolV[Sol].push_back(stiva[st]);

    sort(SolV[Sol].begin(),SolV[Sol].end());
}

inline int min(int a,int b)
{
    return a < b ? a : b;
}

inline int compBiconexe(int a)
{
    int Min1 = viz[a]-1,Min2,nr = 0;
    stiva[++st] = a;

    for(it i=A[a].begin();i<A[a].end();i++)
        if(!viz[*i])
        {
            viz[*i] = viz[a]+1;
            Min2 = compBiconexe(*i);
            if(Min2 >= viz[a])
                adaugaComp(a,*i);
            Min1 = min(Min1,Min2);
            ++ nr;
        }
        else
            Min1 = min(Min1,viz[*i]);

    if(viz[a] == 1 && nr >= 2 && st >= 2)
        adaugaComp(a,stiva[2]);

    return Min1;
}

void Rezolvare(void)
{
    for(int i=1;i<=N;i++)
        if(!viz[i])
    {
        viz[i] = 1;
        compBiconexe(i);
    }

    //for(int i=1;i<=N;i++)
    //    printf("%d ",viz[i]);
}

int main()
{
    citire();
    Rezolvare();

    fprintf(g,"%d\n",Sol);
    for(int i=1;i<=Sol;i++,fprintf(g,"\n"))
        for(it j=SolV[i].begin();j<SolV[i].end();j++)
            fprintf(g,"%d ",*j);
}