Cod sursa(job #913527)

Utilizator GaborGabrielFMI - GabrielG GaborGabriel Data 13 martie 2013 16:47:29
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

const int maxn = 100005;

int num_vertices, num_edges, indecs;

vector<int> idx, low, graph[maxn], sol_aux, in_stack;
vector< vector<int> > sol;
stack<int> s;

int Minim(int a,int b)
{
    if(a>b) return b;
    return a;
}

void Read()
{
    int aux1,aux2;

    f>>num_vertices>>num_edges;

    for(int i=1 ; i<=num_edges ; i++)
    {
        f>>aux1>>aux2;
        graph[aux1].push_back(aux2);
    }

    f.close();
}

void Write()
{
    g<<sol.size()<<'\n';

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

    g.close();
}

void Tarjan(int v)
{
    idx[v] = low[v] = indecs;
    indecs++;

    s.push(v);
    in_stack[v] = 1;

    vector<int>::iterator it;
    for(it=graph[v].begin(); it!=graph[v].end(); ++it)
    {
        if(idx[*it] == -1)
        {
            Tarjan(*it);
            low[v] = Minim(low[v],low[*it]);
        }
        else
            if(in_stack[*it]==1)
                low[v] = Minim(low[v],low[*it]);
    }

    if(low[v] == idx[v])
    {
        sol_aux.clear();

        int node;
        do{
            node = s.top();
            sol_aux.push_back(node);
            in_stack[node]=0;
            s.pop();
        }while(v != node);

        sol.push_back(sol_aux);
    }


}


int main()
{
    Read();

    idx.resize(num_vertices+1), low.resize(num_vertices+1), in_stack.resize(num_vertices+1);
    idx.assign(num_vertices+1, -1), in_stack.assign(num_vertices+1,0);

    for(int i=1; i<=num_vertices; i++)
        if(idx[i] == -1)
            Tarjan(i);

    Write();

    return 0;
}