Cod sursa(job #1713727)

Utilizator Emy1337Micu Emerson Emy1337 Data 6 iunie 2016 13:08:59
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 100005;
int n, m, x, y, nrComp = 0;
int hh[MAXN],viz[MAXN];
vector < int > graph [MAXN];
stack < int > stiva;
vector<int> v[MAXN];

void scoate_componenta(int nod)
{
    ++nrComp;
    while (stiva.top() != nod)
    {
        v[nrComp].push_back(stiva.top());
        stiva.pop();
    }
    v[nrComp].push_back(stiva.top());
}

void dfs (int nod, int depth)
{
    hh[nod] = depth;
    viz[nod] = 1;
    stiva.push(nod);

    int how_high = depth;

    for (auto it : graph[nod] )
    {
        if (viz[it])
            how_high = min(how_high, hh[it]);
        else
        {
            dfs(it, depth + 1);
            how_high = min (how_high, hh[it]);

            if (hh[it] == depth)
            {
                scoate_componenta(nod);
            }
        }
    }
    hh[nod] = how_high;
}

int main()
{
    fin >> n >> m;
    while(m--)
    {
        fin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    for(int i=1; i<=n; i++)
    {
        if(!viz[i])
            dfs(i, 0);
    }
    fout<<nrComp<<endl;
    for(int i=1; i<=nrComp; i++)
    {
        reverse(v[i].begin(), v[i].end());

        for(auto it: v[i])
            fout<<it<<" ";
        fout<<"\n";
    }




}