Cod sursa(job #1376155)

Utilizator httpsLup Vasile https Data 5 martie 2015 16:18:36
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <vector>
#include <fstream>
#include <iostream>
using namespace std;
typedef vector<int> VI;

ifstream f("biconex.in");
ofstream g("biconex.out");

#define foor(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();++it)
#define inf 0x3f3f3f3f

int n,m,x,y,i;
vector<VI> G,comp;
VI stiva,low,lev;
vector<bool> viz;

void dfs(int nod,int level)
{
    viz[nod]=true;
    stiva.push_back(nod);
    lev[nod]=low[nod]=level;

    foor(it,G[nod]) if(!viz[*it])
    {
        dfs(*it,level+1);
        if(low[*it]>=lev[nod])
        {
            comp.resize(comp.size()+1);
            while(stiva.back()!=nod)
            {
                comp.back().push_back(stiva.back());
                stiva.pop_back();
            }
            comp.back().push_back(nod);
        }
        low[nod]=min(low[nod],low[*it]);
    }
    else low[nod]=min(low[nod],lev[*it]);
}

int main()
{
    f>>n>>m;

    G.resize(n+1);
    low.resize(n+1,inf);
    viz.resize(n+1);
    lev.resize(n+1);

    for(;m;--m)
    {
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    for(i=1;i<=n;++i) if(!viz[i]) dfs(i,1),stiva.pop_back();
    g<<comp.size()<<'\n';
    foor(itc,comp)
    {
        foor(it,(*itc)) g<<*it<<' ';
        g<<'\n';
    }
    return 0;
}