Cod sursa(job #3030187)

Utilizator T1raduTaerel Radu Nicolae T1radu Data 17 martie 2023 15:49:29
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 kb
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int c,n,m,tt[100001],nivel[100001],nma[100001],viz[100001],aux;
vector<int> G[100001],sol[100001];
void dfs(int x)
{
    nivel[x]=nivel[tt[x]]+1;
    nma[x]=nivel[x];
    for(vector<int>::iterator it=G[x].begin(); it!=G[x].end(); it++)
    {
        int nod=*it;
        if(nivel[nod]==0)
        {
            tt[nod]=x;
            dfs(nod);
            if(nma[x]>nma[nod]) nma[x]=nma[nod];
            if(nivel[x]<nma[nod])
            {
                sol[++aux].push_back(x);
                sol[aux].push_back(nod);
                G[x].erase(it);
                G[nod].erase(lower_bound(G[nod].begin(),G[nod].end(),x));
                it--;
            }
        }
        else if(nod!=tt[x])
        {
            nma[x]=min(nma[x],nivel[nod]);
        }
    }
}
void dfsc(int x, int aux)
{
    viz[x]=1;
    sol[aux].push_back(x);
    for(vector<int>::iterator it=G[x].begin(); it!=G[x].end(); it++)
    {
        if(viz[*it]==0)
            dfsc(*it,aux);
    }
}
int main()
{
    fin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        int x,y;
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i=1; i<=n; i++)
        sort(G[i].begin(),G[i].end());
    dfs(1);
    aux++;
    for(int i=1; i<=n; i++)
    {
        if(viz[i]==0)
        {
            dfsc(i,aux);
            if(sol[aux].size()!=1)
            {
                aux++;
            }
            else sol[aux].clear();
        }
    }
    aux--;
    fout << aux << "\n";
    for(int i=1; i<=aux; i++)
    {        for(vector<int>::iterator it=sol[i].begin(); it!=sol[i].end(); it++)
            fout << *it << " ";
        fout << "\n";
    }
    return 0;
}