Cod sursa(job #1157206)

Utilizator micadoriAndreea Racovita micadori Data 28 martie 2014 12:30:54
Problema Componente biconexe Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 3.91 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m,nr_comp;
int cicluri[10000],viz[10000];//Lung_ciclu[100];
vector <int> v[10000];
vector <int> c;
vector <int> comp[10000];

int cicluri_complet ()
{
    for (int i=1; i<=n; i++)
        if (cicluri[i]==0)
            return 0;
    return 1;
}

int viz_complet ()
{
    for (int i=1; i<=n; i++)
        if (viz[i]==0)
            return 0;
    return 1;
}

int exista_muchie_c ( int x )
{
    for (int i=0; i<v[x].size(); i++)
        if (cicluri[v[x][i]]==0)
            return v[x][i];
    return 0;
}

int exista_muchie_v ( int x )
{
    for (int i=0; i<v[x].size(); i++)
        if (viz[v[x][i]]==0)
            return v[x][i];
    return 0;
}

int inchide_ciclu ( int x )
{
    int i,j;
    for ( i=0; i<c.size()-2; i++ )
        for ( j=0; j<v[x].size(); j++ )
            if ( c[i]==v[x][j] )
                return i;
    return -1;
}

int calc_nr_comp()
{
    for (int i=0; i<10000; i++)
        if (comp[i].size()==0)
            return i;
}

void completare_cicluri(int x)
{
    int k=0,i,j;
    cicluri[x]=x;
    c.push_back (x);
    while ( !cicluri_complet () )
    {
        i=exista_muchie_c (c[k]); //returneaza nodul
        if (i)
        {
            c.push_back (i);
            k++;
            cicluri[c[k]]=c[k];
            if (k>=2)
            {
                int p=inchide_ciclu (c[k]); //returneaza pozitia inchizatorului in c
                if (p!=-1)
                {
                    j=c.size()-1;
                    while (cicluri[c[j]]!=cicluri[c[p]])
                    {
                        cicluri[c[j]]=cicluri[c[p]];
                        j--;
                    }
                }
            }
        }
        else
        {
            while (!i)
            {
                c.pop_back();
                k--;
                i=exista_muchie_c (c[k]);
            }
        }
    }
    c.clear();
}

void prelucrare(int start, int x)
{
    int i,ok=0;
    for (i=start; i<x; i++)
        if (cicluri[c[i]]==cicluri[c[i+1]])
        {
            /*int t=i;
            while (t<x && cicluri[c[t]]==cicluri[c[t+1]])
                t++;
            if  (Lung_ciclu[c[i]]==t-i)
            {*/
                nr_comp=calc_nr_comp();
            while (i<x && cicluri[c[i]]==cicluri[c[i+1]])
            {
                comp[nr_comp].push_back(c[i]);
                i++;
            }
            comp[nr_comp].push_back(c[i]);
            i--;

        }
        else
        {
            nr_comp=calc_nr_comp();
            comp[nr_comp].push_back(c[i]);
            comp[nr_comp].push_back(c[i+1]);
        }

}

void biconex(int x)
{
    completare_cicluri(x);
    int k=0,i,j,initial=0;
    viz[x]=1;
    c.push_back (x);
    while ( !viz_complet() )
    {
        i=exista_muchie_v (c[k]); //returneaza nodul
        if (i)
        {
            c.push_back (i);
            k++;
            viz[c[k]]=1;

        }
        else
        {
            prelucrare(initial,k);
            while (!i)
            {
                c.pop_back();
                k--;
                i=exista_muchie_v (c[k]);
            }
            initial=k;
        }
    }
    prelucrare(initial,c.size()-1);
    c.clear();
}

int main()
{
    int x,y,i,j; // n=nr noduri
    f>>n;
    f>>m;
    for (i=0; i<m; i++)
    {
        f>>x;
        f>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    biconex(1);
    for (i=0; i<n; i++)
        if (comp[i].size()==0)
        {
            nr_comp=i;
            break;
        }
    g<<nr_comp<<'\n';
    for (i=0; i<nr_comp; i++)
    {
        for (j=0; j<comp[i].size(); j++)
            g<<comp[i][j]<<" ";
        g<<'\n';
    }
    return 0;
}