Cod sursa(job #2850599)

Utilizator AdrianDiaconitaAdrian Diaconita AdrianDiaconita Data 17 februarie 2022 08:44:50
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int NMAX = 100001;
vector <int> Ad[NMAX], biconex[NMAX];
stack <int> S;
int n,m,nrc;
int desc[NMAX], low[NMAX];
bool vis[NMAX];

void DFS(int nod, int parent)
{
    vis[nod] = 1;
    S.push(nod);
    desc[nod] = desc[parent] + 1;
    low[nod] = desc[nod];
    for (int i = 0; i < Ad[nod].size(); ++i)
    {
        int w = Ad[nod][i];
        if (vis[w] == 0)
        {
            DFS(w,nod);
            low[nod] = min (low[nod], low[w]);
            if (low[w] >= desc[nod] && w != parent)
            {
                nrc++;
                S.push(nod);
                while ( !S.empty() && S.top() != w)
                {
                    biconex[nrc].push_back(S.top());
                    S.pop();
                }
                if (!S.empty())
                {
                    biconex[nrc].push_back(S.top());
                    S.pop();
                }
            }
        }
        else if (w != parent)
        {
            low[nod] = min (low[nod], desc[w]);
        }
    }
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int x,y;
        fin >> x >> y;
        Ad[x].push_back(y);
        Ad[y].push_back(x);
    }
    DFS(1,0);
    fout << nrc << '\n';
    for (int i = 1; i <= nrc; ++i)
    {
        for (int j = 0; j < biconex[i].size(); ++j)
            fout << biconex[i][j] << ' ';
        fout << '\n';
    }

    return 0;
}