Cod sursa(job #2368563)

Utilizator Teo_1101Mititelu Teodor Teo_1101 Data 5 martie 2019 16:35:32
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int NMAX = 100002;

int N,M;
int x,y;

int disc[NMAX],d;
int low[NMAX];

bool viz[NMAX];

vector <int> Ad[NMAX];
vector <int> A;

vector <int> S;

int nr_comp;
vector <int> Comp[NMAX];
void DFSA(int nod,int parent)
{
    //viz[nod]=1;
    disc[nod]=low[nod]=++d;
    for(int i=0;i<Ad[nod].size();++i)
    {
        int w=Ad[nod][i];

        if(!disc[w])
        {
            S.push_back(w);
            DFSA(w,nod);
            low[nod]=min(low[nod],low[w]);
            if(low[w] >= disc[nod])
            {
                ++nr_comp;
                S.push_back(nod);
                while(!S.empty() && S.back()!=w)
                {
                    Comp[nr_comp].push_back(S.back());
                    S.pop_back();
                }
                if(!S.empty())
                {
                    Comp[nr_comp].push_back(S.back());
                    S.pop_back();
                }
            }
        }
        else if(w!=parent) low[nod]=min(low[nod],disc[w]);
    }
}
void Read()
{
    fin>>N>>M;
    for(int i=1;i<=M;++i)
    {
        fin>>x>>y;
        Ad[x].push_back(y);
        Ad[y].push_back(x);
    }
    DFSA(1,0);
    fout<<nr_comp<<"\n";
    for(int i=1;i<=nr_comp;++i){
        for(int j=0;j<Comp[i].size();++j)
        fout<<Comp[i][j]<<" ";
    fout<<"\n";}
}
int main()
{
    Read();
    return 0;
}