Cod sursa(job #1423249)

Utilizator batistaUPB-Oprea-Cosmin-Dumitru batista Data 21 aprilie 2015 17:01:19
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <algorithm>
#include <stack>
#include <vector>
#define N 100002

using namespace std;

bool viz[N];
vector <int> v[N];
stack <int> st;
int low_level[N], sol[2*N], poz, nr_ctc;
void dfs(int nd, int niv)
{
    st.push(nd);
    low_level[nd] = niv;
    viz[nd] = 1;
    for(vector<int>::iterator it = v[nd].begin(); it!=v[nd].end(); ++it)
    {
        if(!viz[*it])
            dfs(*it, niv+1);
        low_level[nd] = min(low_level[nd], low_level[*it]);
    }
    /*nodul este radacina a unei componente tare conexa*/
    if(niv == low_level[nd])
    {
        ++nr_ctc;
        while(st.top() != nd)
        {
            sol[poz++] = st.top();
            st.pop();
        }
        sol[poz++] = st.top();
        st.pop();
        /*marchez sfarsitul primei comonente*/
        sol[poz++] = -1;
    }
}
int main()
{
    int i, n, m, x, y;
    ifstream f("ctc.in");
    ofstream g("ctc.out");
    f >> n >> m;
    for(i=0; i<m; ++i)
    {
        f >> x >> y;
        v[x].push_back(y);
    }
    for(i=1; i<=n; ++i)
        if(!viz[i]) dfs(i, 0);
    g << nr_ctc << "\n";
    for(i=0; i<poz; ++i)
    {
        while(i<poz && sol[i] != -1)
        {
            g << sol[i] << " ";
            ++i;
        }
        g<< "\n";
    }
    f.close();
    g.close();
    return 0;
}