Cod sursa(job #751807)

Utilizator Theorytheo .c Theory Data 26 mai 2012 23:32:38
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.17 kb
#include<fstream>
#include<vector>
#include<stdio.h>
#include<stdlib.h>
#include<stack>
#include<algorithm>
#define nmax 100005
using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

struct muchie {int d1, d2;};
int n, *A[nmax], m;
int low[nmax], Niv[nmax], T[nmax], Vf, Atinge;
bool viz[nmax];
muchie S[200005];
vector <int> v[nmax * 2];
int nr_comp_biconexe;

inline int mini(int a,int  b)
{
   return a > b ? b : a;
}

inline void adauga(int nod, int tata)
{
    int a=0, b=0;
    while( a!= nod &&  b != tata)
    {
        a = S[Vf].d1;
        b = S[Vf].d2;
        --Vf;
        v[nr_comp_biconexe].push_back(a);

    }
    v[nr_comp_biconexe].push_back(tata);
    nr_comp_biconexe++;
}

void DFS(int nod)
{
    int y,i ;
    low[nod] = Niv[nod];
    for(i = 1; i <= A[nod][0] ; i++)
    {
        y = A[nod][i];
        if(Niv[y] == 0 )
        {

            T[y] = nod;
            S[++Vf].d1 = y;
            S[Vf].d2 = nod;

            Niv[y] = Niv[nod] + 1;
            DFS(y);
            low[nod] = mini(low[y], low[nod] );
            if(low[y] >= Niv[nod])// nu pot ajunge mai sus decat tatal nodului y in arbore-> nod critic
                adauga(y, nod);

        }
        else
            if(y != T[nod])
                low[nod] = mini(low[nod], Niv[y]);

    }
}

void read()
{
    int x, y;
    fin >> n >> m;

    for(int  i=1; i <= n ;++i)
    {
        A[i] = (int *) realloc(A[i], sizeof(int));
        A[i][0] = 0;
    }

    for(int i = 1; i <= m ; i++)
    {

        fin >> x >>y;
        A[x][0]++;
        A[y][0]++;
        A[x] = (int *) realloc(A[x],sizeof(int) * (A[x][0] + 1 ));
        A[x][A[x][0]] = y;
        A[y] = (int *) realloc(A[y], sizeof(int) * (A[y][0] + 1));
        A[y][A[y][0]] = x;

    }


}
int main()
{
      read();
      Niv[1] = 1;
    DFS(1);
    fout << nr_comp_biconexe <<'\n';
    for(int i = 0 ;i < nr_comp_biconexe; ++i)
    {
        sort(v[i].begin(), v[i].end());
        for(int j = 0 ;j < v[i].size(); j++ )
            fout << v[i][j] << " " ;
        fout <<'\n';
    }
    fin.close();
    return 0;
}