Cod sursa(job #1379026)

Utilizator heracleRadu Muntean heracle Data 6 martie 2015 15:48:10
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.94 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>

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

const int Q=100007,W=200007;

int lst[Q],val[2*W],nxt[2*W],nr;

void add(int a, int b)
{
    val[++nr]=b;
    nxt[nr]=lst[a];
    lst[a]=nr;
}

int n,m;

int viz[Q];

int h[Q];

std::stack<int> s;

std::vector<int> comp[Q];

int up[Q];

int c[2*W];

int nrcomp;

void dfs(int nod)
{
    viz[nod]=1;

    for(int p=lst[nod]; p; p=nxt[p])
    {
        if(viz[val[p]]==0)
        {
            s.push(p);

            h[val[p]]=h[nod]+1;

            dfs(val[p]);

            if(up[val[p]]==nod)
            {
                nrcomp++;
                while(s.top()!=p)
                {
                    c[s.top()]=nrcomp;
                    s.pop();
                }
                c[s.top()]=nrcomp;
                s.pop();
            }

            if(h[up[val[p]]] < h[up[nod]])
                up[nod]=up[val[p]];

        }
        if(viz[val[p]]==1)
        {
            if(h[val[p]] < h[up[nod]])
            {
                up[nod]=val[p];
            }
        }
    }

    viz[nod]=2;
}

int main()
{
    fscanf(in,"%d%d",&n,&m);

    int a,b;

    for(int i=1; i<=m; i++)
    {
        fscanf(in,"%d%d",&a,&b);

        add(a,b);
        add(b,a);
    }

    h[0]=Q;

    h[1]=1;
    dfs(1);

    fprintf(out,"%d\n",nrcomp);

    for(int i=1; i<=n; i++)
    {
        int p=lst[i];

        while(p)
        {
            if(c[p]!=0)
            {
                comp[c[p]].push_back(i);
                comp[c[p]].push_back(val[p]);
            }

            p=nxt[p];
        }
    }

    for(int i=1; i<=nrcomp; i++)
    {
        std::sort(comp[i].begin(), comp[i].end());
        fprintf(out,"%d ",comp[i][0]);

        for(int j=1; j<comp[i].size(); j++)
        {
            if(comp[i][j]!=comp[i][j-1])
                fprintf(out,"%d ",comp[i][j]);
        }

        fprintf(out,"\n");
    }

    return 0;
}