Cod sursa(job #1645969)

Utilizator roxana.aeleneiAelenei Roxana roxana.aelenei Data 10 martie 2016 14:32:39
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int NMAX=100000;
int n,m;
struct muchie
{
    int x,y;
}S[NMAX];
vector <int> G[NMAX+2],sol[NMAX+2];
bool artic_vertex[NMAX+2];
int low[NMAX+2], disc[NMAX+2], dad[NMAX+2];
int time,root,child,k,nr;

void articPoint(int u)
{

    int v;
    ++time;
    disc[u]=low[u]=time;
    for(int j=0; j<(int)G[u].size(); j++)
    {
        v=G[u][j];
        if(!disc[v])
        {
            k++;
            S[k].x=u;
            S[k].y=v;
            dad[v]=u;

            articPoint(v);
            if(low[v] >= disc[u])
               {
                   nr++;
                   int a,b;
                   do{
                   a=S[k].x;
                   b=S[k].y;
                   k--;
                   sol[nr].push_back(b);
                   }while(a!=u && b!=v);
                   sol[nr].push_back(u);


               }
            low[u]=min(low[u], low[v]);
        }
        else
           if (v != dad[u])
                low[u]=min(low[u],low[v]);
    }

}



int main()
{
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);

    scanf("%d%d", &n, &m);

    for(int i=1; i<=m; i++)
    {
        int u,v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }

    for(int i=1; i<=n; i++)
        dad[i]=-1;

    for(int i=1; i<=n; i++)
    if(!disc[i])
        articPoint(i);

    printf("%d\n", nr);

    for(int i=1; i<=nr; i++)
        {
            for(int j=0; j<(int)sol[i].size(); j++)
            printf("%d ", sol[i][j]);

            printf("\n");
        }
    return 0;
}