Cod sursa(job #2013014)

Utilizator NannyiMaslinca Alecsandru Mihai Nannyi Data 20 august 2017 02:28:07
Problema Componente biconexe Scor 42
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <stack>
#include <queue>
using namespace std;

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

vector <int> Q[100001];
vector<int> Z1,Z2;
stack<int>Z3;
vector< stack < int > >QQ;

int n,m,nrcomp;

void afisare(int limita)
{
    stack<int>Z4;
    int cnod;
    do
    {
        cnod=Z3.top();
        Z4.push(cnod);
        Z3.pop();
    }
    while(cnod!=limita);
    Z3.push(limita);
    QQ.push_back(Z4);
    ++nrcomp;
}

void dfs(int nod,int tata,int numar)
{
    Z1[nod]=Z2[nod]=numar;
    for (vector<int>::iterator it=Q[nod].begin(); it!=Q[nod].end(); ++it)
    {
        if (*it==tata)continue;
        if (Z1[*it]==-1)
        {
            Z3.push(*it);
            dfs(*it,nod,numar+1);
            Z2[nod]=min(Z2[nod],Z2[*it]);
            if (Z2[*it]>=Z1[nod])
                afisare(nod);
        }
        else
            Z2[nod]=min(Z2[nod],Z1[*it]);
    }
}


void citire()
{
    int a,b;
    f>>n>>m;
    while (f>>a>>b)
    {
        Q[b].push_back(a);
        Q[a].push_back(b);
    }
}

int main()
{
    citire();
    Z1.resize(n+1);
    Z1.assign(n+1,-1);
    Z2.resize(n+1);
    Z3.push(1);
    dfs(1,0,0);
    g<<nrcomp<<'\n';
    for (int c=0;c<nrcomp;++c)
    {
        while (!QQ[c].empty())
            g<<QQ[c].top()<<' ',QQ[c].pop();
        g<<'\n';
    }
    return 0;
}