Cod sursa(job #2372766)

Utilizator alexandra_paticaAndreea Alexandra Patica alexandra_patica Data 7 martie 2019 11:01:38
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream f ("meh.in");
ofstream g ("meh.out");

int t1[100010], t2[100010], st[100010];
int nr, n, m, nr_componente, k, x, y;
bool viz[100010];
vector<int> sol[100010], G[100010];

void dfs (int x)
{
    nr++;
    t1[x]=t2[x]=nr;
    viz[x]=1;
    st[++k]=x;

    for (int i=0; i<G[x].size(); i++)
    {
        if (!viz[G[x][i]])
        {
            int y=k;
            dfs(G[x][i]);

            t2[x]=min(t2[x], t2[G[x][i]]);
            if (t2[G[x][i]]>=t1[x])
            {
                nr_componente++;
                while (k>y)
                {
                    sol[nr_componente].push_back(st[k]);
                    k--;
                }
                sol[nr_componente].push_back(x);
            }
        }

        else t2[x]=min(t2[x], t1[G[x][i]]);
    }
}


int main ()
{
    f >> n >> m;
    for (int i=1; i<=m; i++)
    {
        f >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    dfs(1);

    g << nr_componente << '\n';

    for (int i=1; i<=nr_componente; i++)
    {
        for (int j=0; j<sol[i].size(); j++)
            g << sol[i][j] << " ";
        g << '\n';
    }
    return 0;
}