Cod sursa(job #1378064)

Utilizator httpsLup Vasile https Data 6 martie 2015 10:23:45
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 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,int fat)
    {
    viz[nod]=true;
    stiva.push_back(nod);
    lev[nod]=low[nod]=level;

    foor(it,G[nod])
        {
        if(!viz[*it])
            {
            dfs(*it,level+1,nod);
            if(low[*it]>=lev[nod])
                {
                comp.resize(comp.size()+1);
                while(stiva.back()!=*it)
                    {
                    comp.back().push_back(stiva.back());
                    stiva.pop_back();
                    }
                comp.back().push_back(nod);
                comp.back().push_back(*it);
                stiva.pop_back();
                }
            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,0);
            stiva.pop_back();
            /*if(G[i].size()==0)
                {
                comp.resize(comp.size()+1);
                comp.back().push_back(i);
                }*/
            }
    g<<comp.size()<<'\n';
    foor(itc,comp)
        {
        foor(it,(*itc)) g<<*it<<' ';
        g<<'\n';
        }
    return 0;
    }