Cod sursa(job #2409410)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 18 aprilie 2019 23:30:12
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int VAL=100005;

int N, M, i, j, A, B;
int st[VAL], top, low[VAL];
int NRCOMP, niv[VAL], X;
bool ok[VAL];
vector <int> G[VAL];
vector <int> COMP[VAL];

void DFS(int nod, int FAT, int level)
{
    vector <int> :: iterator it;
    ok[nod]=true;
    niv[nod]=low[nod]=level;
    st[++top]=nod;
    for (it=G[nod].begin(); it!=G[nod].end(); it++)
    {
        if (*it==FAT)
            continue;
        if (ok[*it]==true)
        {
            low[nod]=min(low[nod], niv[*it]);
            continue;
        }
        DFS(*it, nod, level+1);
        low[nod]=min(low[nod], low[*it]);
        if (niv[nod]<=low[*it])
        {
            NRCOMP++;
            while (top>0)
            {
                COMP[NRCOMP].push_back(st[top]);
                if (st[top]==*it)
                {
                    top--;
                    break;
                }
                top--;
            }
            COMP[NRCOMP].push_back(st[top]);
        }
    }
}

int main()
{
    fin >> N >> M;
    for (i=1; i<=M; i++)
    {
        fin >> A >> B;
        G[A].push_back(B);
        G[B].push_back(A);
    }
    for (i=1; i<=N; i++)
        if (ok[i]==false)
            DFS(i, 0, 1);
    fout << NRCOMP << '\n';
    for (i=1; i<=NRCOMP; i++)
    {
        for (j=0; j<COMP[i].size(); j++)
            fout << COMP[i][j] << " ";
        fout << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}