Cod sursa(job #1232215)

Utilizator AdrianaMAdriana Moisil AdrianaM Data 22 septembrie 2014 14:20:15
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <fstream>
#include <vector>
#include <stack>
#define INF 0x3f3f3f3f
using namespace std;

ifstream is("ctc.in");
ofstream os("ctc.out");

int n, m, a, b;
int nrg; // nrg = indecs
vector<vector<int> > g, c; // g - vecini, c - ctc
vector<int> grup, gmin, con; // idx, lowlink
vector<bool> ok; // in_stack
stack<int> s;

void TARJAN(int nod);

int main()
{
    is >> n >> m;
    g.resize(n + 1);
    for ( int i = 1; i <= m; ++i )
    {
        is >> a >> b;
        g[a].push_back(b);
    }
    grup.resize(n + 1, INF);
    gmin.resize(n + 1);
    ok.resize(n + 1);
    for ( int i = 1; i <= n; ++i )
    {
        if ( grup[i] == INF )
            TARJAN(i);
    }
    os << c.size() << "\n";
    for ( size_t i = 0; i < c.size(); ++i )
    {
        for ( size_t j = 0; j < c[i].size(); ++j )
            os << c[i][j] << " ";
        os << "\n";
    }
    is.close();
    os.close();
    return 0;
}

void TARJAN(int nod)
{
    grup[nod] = gmin[nod] = nrg; // grup = idx, gmin = lowlink
    ++nrg;
    s.push(nod);
    ok[nod] = true;
    for ( vector<int>::iterator it = g[nod].begin(); it != g[nod].end(); ++it )
    {
        if ( grup[*it] == INF )
        {
            TARJAN(*it);
            gmin[nod] = min(gmin[nod], gmin[*it]);
        }
        else
            if ( ok[*it] )
                gmin[nod] = min(gmin[nod], gmin[*it]);
    }
    if ( grup[nod] == gmin[nod] )
    {
        con.clear();
        int nod2;
        do
        {
            con.push_back(nod2 = s.top());
            s.pop();
            ok[nod2] = false;
        } while ( nod2 != nod );
        c.push_back(con);
    }
}