Cod sursa(job #1929284)

Utilizator LazarAndreiLazar Andrei Teodor LazarAndrei Data 17 martie 2017 13:51:06
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <bits/stdc++.h>
using namespace std;

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

const int NMAX = 100005;

vector <int> G[NMAX];
vector <int> CTC[100000];
int label[NMAX], lowlink[NMAX], index, nr, nodes, edges;
bool in_stack[NMAX];
stack <int> S;


void StrongCon (int node) {
    int  w;
    label[node] = index;
    lowlink[node] = index;
    ++ index;
    S.push(node);
    in_stack[node] = true;

    for (auto &it: G[node]) {
        if (label[it] == -1) {
            StrongCon (it);
            lowlink[node] = min (lowlink[node], lowlink[it]);
        }
        else if (in_stack[it]) {
            lowlink[node] = min (lowlink[node], lowlink[it]);
        }
    }

    if (lowlink[node] == label[node]) {
        ++ nr;
        do
        {
            w = S.top ();
            S.pop ();
            in_stack[w] = false;
            CTC[nr].push_back(w);

        }while (node != w);
    }
}

int main()
{
    in >> nodes >> edges;

    for (int i = 1; i <= edges; ++ i) {
        int from, to;
        in >> from >> to;
        G[from].push_back(to);
    }

    for (int i = 1; i <= nodes; ++ i) {
        label[i] = -1;
    }

    for (int i = 1; i <= nodes; ++ i) {
        if (label[i] == -1) {
            StrongCon (i);
        }
    }

    out << nr << '\n';
    for (int i = 1; i <= nr; ++ i) {
        for (auto &it: CTC[i]) {
            out << it << " ";
        }
        out << '\n';
    }

   return 0;
}