Cod sursa(job #1132413)

Utilizator denisx304Visan Denis denisx304 Data 3 martie 2014 10:45:54
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb

#include <fstream>
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

#define no_nodes 100001

vector <int> my_nodes[no_nodes], scc[no_nodes];
stack <int> my_stack;
int bStack[no_nodes], index[no_nodes], LowLink[no_nodes], n, m, no_scc = 0, Index = 0;

void Tarjan(int t)
{
    index[t] = Index;
    LowLink[t] = Index;
    Index ++;
    my_stack.push(t);
    bStack[t] = 1;

    for (int i = 0; i < my_nodes[t].size(); i ++)
        if (index[my_nodes[t][i]] == -1)
    {
        Tarjan(my_nodes[t][i]);
        LowLink[t] = min(LowLink[t], LowLink[my_nodes[t][i]]);
    }
        else
            if (bStack[my_nodes[t][i]])
                LowLink[t] = min(LowLink[t], index[my_nodes[t][i]]);

    if (LowLink[t] == index[t])
    {
        int temp;
        do
        {
            temp = my_stack.top();
            bStack[temp] = 0;
            scc[no_scc].push_back(temp);
            my_stack.pop();
        }
        while (temp != t);
        no_scc ++;
    }
}

int main()
{
    int t1, t2;

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

    f >> n >> m;

    for (int i = 1; i <= m; i ++)
    {
        f >> t1 >> t2;
        my_nodes[t1].push_back(t2);
    }
    for (int i = 1; i <= n; i ++)
    {
        bStack[i] = 0;
        index[i] = -1;
    }

    for (int i = 1; i <= n; i ++)
        if (index[i] == -1)
            Tarjan(i);

    g << no_scc << '\n';

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

    f.close();
    g.close();

    return 0;
}