Cod sursa(job #1971437)

Utilizator GinguIonutGinguIonut GinguIonut Data 20 aprilie 2017 13:56:31
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <fstream>
#include <vector>
#include <string.h>

#define INF 2000000000
#define nMax 100001
#define confMax (1 << 18)
#define pb push_back
#define mkp make_pair

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

int n, m, nrcbc;
int lev[nMax], low[nMax];
vector<int> G[nMax], cbc[nMax], stck;


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

    for(vector<int>::iterator it=G[node].begin(); it!=G[node].end(); it++)
    {
        int fiu=*it;
        if(lev[fiu]==0)
        {
            tarjan(fiu, lvl+1);
            low[node]=min(low[node], low[fiu]);

            if(low[fiu]>=lev[node])
            {
                nrcbc++;
                cbc[nrcbc].pb(node);
                int nodeAux;
                do
                {
                    nodeAux=stck.back();
                    stck.pop_back();
                    cbc[nrcbc].pb(nodeAux);
                }
                while(nodeAux!=fiu);
            }
        }
        else
            low[node]=min(low[node], lev[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, 1);

    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';
    }
}