Cod sursa(job #1447501)

Utilizator florinasAsavei florinas Data 4 iunie 2015 17:08:41
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <vector>
#include <stack>

#define NMax 100010

using namespace std;

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

int nodes, edges, prenum[NMax], low[NMax], inc, k;
bool mark[NMax], inStack[NMax];
vector<int> G[NMax], Sol[NMax];
stack<int> S;

int getmin(int a, int b)
{
    if (a < b)
        return a;
    return b;
}

void TARJANdfs(int node)
{
    mark[node] = true;

    S.push(node);
    inStack[node] = true;

    prenum[node] = ++inc;
    low[node] = prenum[node];

    for (vector<int>::iterator it = G[node].begin(); it != G[node].end(); it++) {

        if (!mark[*it]) {
            TARJANdfs(*it);
            low[node] = getmin(low[node], low[*it]);
        }
        else
            if (inStack[*it])
                low[node] = getmin(low[node], prenum[*it]);

    }

    if (low[node] == prenum[node]) {

        int u;
        k++;
        do {
            u = S.top();
            Sol[k].push_back(u);
            inStack[u] = false;
            S.pop();
        } while (u != node);

    }
}

int main()
{

    f >> nodes >> edges;
    int n1, n2;
    for (int i = 1; i <= edges; i++) {
        f >> n1 >> n2;

        G[n1].push_back(n2);
    }

    for (int i = 1; i <= nodes; i++)
        if (!mark[i])
            TARJANdfs(i);

    g << k << "\n";
    for (int i = 1; i <= k; i++) {
        for (vector<int>::iterator it = Sol[i].begin(); it != Sol[i].end(); it++)
            g << *it << " ";
        g<<"\n";
    }

    return 0;
}