Cod sursa(job #1861279)

Utilizator GinguIonutGinguIonut GinguIonut Data 28 ianuarie 2017 19:03:53
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <vector>

#define nMax 100001
#define pb push_back
using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m, nrCbc;
int lev[nMax], low[nMax];
vector<int> G[nMax],  stck, cbc[nMax];

void tarjan(int node, int tata)
{
    lev[node]=low[node]=lev[tata]+1;
    stck.pb(node);

    for(vector<int>::iterator it=G[node].begin(); it!=G[node].end(); it++)
    {
        int fiu=*it;
        if(lev[fiu])
            low[node]=min(low[node], lev[fiu]);
        else
        {
            tarjan(fiu, node);
            low[node]=min(low[node], low[fiu]);
            if(low[fiu]>=lev[node])
            {
                int son;
                nrCbc++;
                cbc[nrCbc].pb(node);
                do
                {
                    son=stck.back();
                    stck.pop_back();
                    cbc[nrCbc].pb(son);
                }
                while(son!=fiu);
            }
        }
    }
}

int main()
{
    int a,b;
    fin>>n>>m;
    for(int i=1;  i<=m; i++)
    {
        fin>>a>>b;
        G[a].pb(b);
        G[b].pb(a);
    }
    for(int i=1; i<=n; i++)
        if(lev[i]==0)
            tarjan(i, 0);
    fout<<nrCbc<<'\n';
    for(int i=1; i<=nrCbc; i++)
    {
        for(vector<int>::iterator it=cbc[i].begin(); it!=cbc[i].end(); it++)
            fout<<*it<<" ";
        fout<<'\n';
    }
}