Cod sursa(job #2440117)

Utilizator PopescuAndreiAlexandruPopescu Andrei Alexandru PopescuAndreiAlexandru Data 17 iulie 2019 16:37:52
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

#define nmax 100005

int n,m,x,y,stiva[nmax],sf=0,viz[nmax],level[nmax],low[nmax],h=0,k=0;

vector <int> v[nmax];
vector <int> S[nmax];

void dfs(int nod)
{
    sf++;
    h++;
    stiva[sf]=nod;
    vector <int> ::iterator it;
    for(it=v[nod].begin();it!=v[nod].end();it++)
    {
        if(!viz[*it])
        {
            int x=h;
            viz[*it]=1;
            level[*it]=level[nod]+1;
            low[*it]=level[nod]+1;
            dfs(*it);
            low[nod]=min(low[nod],low[*it]);
            if(low[*it]>=level[nod])
            {
                k++;
                S[k].push_back(nod);
                while(h>x)
                {
                    h--;
                    S[k].push_back(stiva[sf]);
                    sf--;
                }
            }
        }
        low[nod]=min(low[nod],level[*it]);
    }
}

int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    level[1]=1;
    low[1]=1;
    dfs(1);
    fout<<k<<'\n';
    for(int i=1;i<=k;i++)
    {
        vector <int> ::iterator it;
        for(it=S[i].begin();it!=S[i].end();it++)
            fout<<*it<<" ";
        fout<<'\n';
    }
}