Cod sursa(job #905133)

Utilizator hoffen42FMI Ana hoffen42 Data 5 martie 2013 16:44:37
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include <iostream>
#include <fstream>
#include <iterator>
#include <vector>
#include <stack>

using namespace std;

#define MAXN 100005
#define min(a, b) ((a) < (b) ? (a) : (b))

vector <int> adj[MAXN], idx, lowlink, stiva, comp;

vector < vector <int> > sol;

stack <int> s;

int index;

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

void read (vector <int> *adj, int &n)
{
    int m, x, y;

    in >> n;
    for (in >> m; m > 0; -- m)
    {
        in >> x >> y;
        x --, y --;
        adj[x].push_back(y);
    }
}

void print(const vector < vector <int> > &G)
{
    out << G.size() << "\n";

    for(size_t i = 0; i < G.size(); ++ i)
    {
        for(size_t j = 0; j < G[i].size(); ++ j)
            out << G[i][j] + 1 << " ";
        out << "\n";
    }

}

void tarjan (const int n, const vector <int> *adj)
{
    idx[n] = lowlink[n] = index;
    index++;
    s.push(n);
    stiva[n] = 1;

    vector <int>::const_iterator it;
    for( it = adj[n].begin(); it != adj[n].end(); ++it)
    {
        if(idx[*it] == -1)
        {
            tarjan(*it, adj);
            lowlink[n] = min(lowlink[n], lowlink[*it]);
        }
        else
            if(stiva[*it])
                lowlink[n] = min(lowlink[n], lowlink[*it]);
    }
        if(idx[n] == lowlink[n])
        {
            comp.clear();
            int nod;
            do{
                nod = s.top();
                comp.push_back(nod);
                s.pop();
                stiva[nod] = 0;
            }
            while (nod != n);
            sol.push_back(comp);
        }

}

int main()
{
    int n;
    read(adj, n);

    idx.resize(n); idx.assign(n, -1);
    stiva.resize(n); stiva.assign(n, 0);
    lowlink.resize(n);

    for(int i = 0; i < n; ++ i)
        if(idx[i] == -1)
            tarjan(i, adj);

    print(sol);
    return 0;
}