Cod sursa(job #2369290)

Utilizator BiancaMariaVulsanVulsan Bianca Maria BiancaMariaVulsan Data 5 martie 2019 22:13:12
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
#define nmax 100003
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m, niv[nmax], low[nmax], viz[nmax], nr;
vector <int> v[nmax], cbc[nmax];
stack<int> s;

void citire()
{
    int i,x,y;
    f>>n>>m;
    for(i=1; i<=m; i++)
    {
        f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
}

void dfs(int nod, int tata)
{
    int i,next,vf;
    s.push(nod);
    niv[nod]=niv[tata]+1;
    low[nod]=niv[nod];
    viz[nod]=1;
    for(i=0; i<v[nod].size(); i++)
    {
        next=v[nod][i];
        if(next!=tata)
        {
            if(viz[next])
            {
                if(low[nod]>niv[next])
                    low[nod]=niv[next];
            }
            else
            {
                dfs(next,nod);
                if(low[nod]>low[next])
                   low[nod]=low[next];

                if(niv[nod]<=low[next])
                {
                    vf=s.top();
                    while(vf!=next)
                    {
                        cbc[nr].push_back(vf);
                        s.pop();
                        vf=s.top();
                    }
                    cbc[nr].push_back(next);
                    s.pop();
                    cbc[nr].push_back(nod);
                    nr++;
                }
            }
        }
    }
}

int main()
{
    citire();
    dfs(1,0);
    int i,j;
    g<<nr<<"\n";
    for(i=0; i<nr; i++)
    {for(j=0; j<cbc[i].size(); j++)
        g<<cbc[i][j]<<" ";
            g<<"\n";}
    f.close();
    g.close();
    return 0;
}