Cod sursa(job #2564180)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 1 martie 2020 18:52:26
Problema Componente biconexe Scor 64
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include <fstream>
#include <vector>
#define NMAX 100002
using namespace std;

ifstream cin("biconex.in");
ofstream cout("biconex.out");

struct muchie
{
    int x,y;
} aux;

vector <int> v[NMAX],rez[NMAX];
vector<muchie> stiva;
int tata[NMAX],disc[NMAX],low[NMAX],t,nrbiconex;

void dfs(int nod)
{
    disc[nod]=low[nod]=++t;
    for(vector<int>::iterator it=v[nod].begin(); it!=v[nod].end(); it++)
    {
        int urm=*it;
        if(!disc[urm])
        {
            tata[urm]=nod;
            aux.x=nod;
            aux.y=urm;
            stiva.push_back(aux);
            dfs(urm);
            low[nod]=min(low[nod],low[urm]);
            if(disc[nod]<=low[urm])
            {
                nrbiconex++;
                rez[nrbiconex].push_back(stiva.back().y);
                while(stiva.back().x!=nod)
                {
                    rez[nrbiconex].push_back(stiva.back().x);
                    stiva.pop_back();
                }
                rez[nrbiconex].push_back(nod);
                stiva.pop_back();
            }
        }
        else if(urm!=tata[nod])
            low[nod]=min(low[nod],disc[urm]);
    }
}

int main()
{
    int i,x,y,n,m;
    cin>>n>>m;
    for(i=1; i<=m; i++)
    {
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(i=1; i<=n; i++)
    {
        if(!disc[i])
        {
            t=0;
            dfs(i);
        }
    }
    cout<<nrbiconex<<'\n';
    for(i=1; i<=nrbiconex; i++)
    {
        for(vector<int>::iterator it=rez[i].begin(); it!=rez[i].end(); it++)
            cout<<*it<<' ';
        cout<<'\n';
    }
    return 0;
}