Cod sursa(job #741231)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 25 aprilie 2012 18:27:47
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

const int MAX = 100050;

int n, index, idx[MAX], lowlink[MAX], in_stack[MAX];
vector<int> v[MAX], con; vector< vector < int > > sol;
stack<int> stk;

void citire()
{
    ifstream in("ctc.in");
    int m, a, b;
    in>>n>>m;
    while(m--)
    {
        in>>a>>b;
        v[a].push_back(b);
    }
    in.close();
}

void init()
{
    for(int i = 1; i <= n; i++)
    {
        idx[i] = lowlink[i] = -1;
        in_stack[i] = 0;
    }
}

void tarjan(int n)
{
    idx[n] = lowlink[n] = index; index++;
    stk.push(n); in_stack[n] = 1;
    for(vector<int>::iterator it = v[n].begin(); it != v[n].end(); it++)
    {
        if(idx[*it] == -1)
        {
            tarjan(*it);
            lowlink[n] = min(lowlink[n], lowlink[*it]);
        }
        else if(in_stack[*it])
            lowlink[n] = min(lowlink[n], lowlink[*it]);
    }
    if(idx[n] == lowlink[n])
    {
        con.clear();
        int nod;
        do
        {
            con.push_back(nod = stk.top());
            stk.pop(); in_stack[nod] = 0;
        }while(nod != n);
        sol.push_back(con);
    }
}

void solve()
{
    for(int i = 1; i <= n; i++)
        if(idx[i] == -1)
            tarjan(i);
}

void afisare()
{
    ofstream out("ctc.out");
    out<<sol.size()<<'\n';
    for(size_t i = 0; i < sol.size(); i++)
    {
        for(size_t j = 0; j < sol[i].size(); j++)
            out<<sol[i][j]<<" ";
        out<<'\n';
    }
    out.close();
}

int main()
{
    citire();
    init();
    solve();
    afisare();
    return 0;
}