Cod sursa(job #2397711)

Utilizator ianiIani Biro iani Data 4 aprilie 2019 18:24:14
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>

#define NMAX 100005

using namespace std;

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

struct nod
{
    int v;
    nod *next;
}*a[NMAX];

int ap[NMAX],nivel[NMAX],nma[NMAX],nrcomp;

stack<int> stk;
vector<int> out[NMAX];

void dfs(int x,int tata)
{
    ap[x]=true;
    stk.push(x);
    nivel[x]=nivel[tata]+1;
    nma[x]=nivel[x];
    for (nod* j=a[x];j;j=j->next)
        if (j->v!=tata)
        {
            if (ap[j->v]==true)
            {
                ///muchie de intoarcere
                if (nma[x]>nivel[j->v])
                    nma[x]=nivel[j->v];
            }
            else
            {
                ///muchie normala
                dfs(j->v,x);
                if (nma[x]>nma[j->v])
                    nma[x]=nma[j->v];
                if (nivel[x]<=nma[j->v])
                {
                    nrcomp++;
                    while(stk.top()!=j->v)
                    {
                        out[nrcomp].push_back(stk.top());
                        stk.pop();
                    }
                    out[nrcomp].push_back(j->v);
                    stk.pop();
                    out[nrcomp].push_back(x);
                }
            }
        }
}

int main()
{
    int n,m;
    fin>>n>>m;
    for (int i=0;i<m;i++)
    {
        int x,y;
        fin>>x>>y;
        nod *nou=new nod;
        nou->v=y;
        nou->next=a[x];
        a[x]=nou;
        nou=new nod;
        nou->v=x;
        nou->next=a[y];
        a[y]=nou;
    }
    dfs(1, 0);
    fout<<nrcomp<<'\n';
    for(int i=1;i<=nrcomp;i++)
    {
        for(auto& value : out[i])
            fout<<value<<' ';
        fout<<'\n';
    }
    return 0;
}