Cod sursa(job #2229705)

Utilizator tanasaradutanasaradu tanasaradu Data 7 august 2018 22:40:02
Problema Componente biconexe Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <bits/stdc++.h>



using namespace std;

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

const int NMAX = 100005;

const int MOD = 666013;

int f[NMAX] , G[NMAX] , niv[NMAX] , n , m , nr;

bool viz[NMAX] , art[NMAX];

vector < int > L[NMAX];

vector < int > sol[NMAX];

stack < int > st;

void DFS(int node)
{
    viz[node] = true;
    G[node] = niv[node];
    st . push(node);
    for(auto it : L[node])
        if(!viz[it])
    {
        niv[it] = niv[node] + 1;
        f[it] = node;
        DFS(it);
        if(G[node] > G[it])
            G[node] = G[it];
        if(G[it] >= niv[node])
        {
            ++nr;
            do
            {
                sol[nr] . push_back(st . top()) , st . pop();
            }
            while(! st.empty() && st . top() != it);
            sol[nr] . push_back(node);
            cout << nr << "\n";
        }
    }
     else if(it != f[node] && G[node] > niv[it])
            G[node] = niv[it];
}

int main()
{
    int x , y;
    fin >> n >> m;
    while(m--)
    {
        fin >> x >> y;
        L[x] . push_back(y);
        L[y] . push_back(x);
    }
    for(int i = 1 ; i <= n ; i++)
        if(!viz[i])
            f[i] = 0 , DFS(i);
    fout << nr << "\n";
    for(int i = 1 ; i <= nr ; i++)
    {
        for(auto it : sol[i])
            fout << it << " ";
        fout << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}