Cod sursa(job #1423265)

Utilizator batistaUPB-Oprea-Cosmin-Dumitru batista Data 21 aprilie 2015 17:15:27
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <algorithm>
#include <stack>
#include <vector>
#define N 100002

using namespace std;

bool viz[N], in_stack[N];
vector <int> v[N];
stack <int> st;
int low_level[N], idx[N], sol[2*N], poz, nr_ctc, index;
void dfs(int nd)
{
    st.push(nd);
    in_stack[nd] = 1;
    idx[nd] = low_level[nd] = ++index;
    viz[nd] = 1;
    for(vector<int>::iterator it = v[nd].begin(); it!=v[nd].end(); ++it)
    {
        if(!viz[*it])
        {
            dfs(*it);
            low_level[nd] = min(low_level[nd], low_level[*it]);
        }
        else if(in_stack[*it])
            low_level[nd] = min(low_level[nd], low_level[*it]);
    }
    /*nodul este radacina a unei componente tare conexa*/
    if(idx[nd] == low_level[nd])
    {
        ++nr_ctc;
        int node;
        do
        {
            node = st.top();
            sol[poz++] = node;
            in_stack[node] = 0;
            st.pop();
        }while(node != nd);
        /*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);
    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;
}