Cod sursa(job #1919180)

Utilizator TarmureSerban99Tarmure Dan Serban TarmureSerban99 Data 9 martie 2017 18:15:23
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <fstream>
#include <stack>
#include <vector>
#define NMAX 100005
using namespace std;

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

int n, m, deep_x, nivmax[NMAX], LONGG[NMAX], NR;
vector <int> G[NMAX], ctc[NMAX];
stack <int> oComponenta;
bool viz[NMAX];

void tarjan (int x) {
    ++deep_x;
    nivmax[x] = deep_x;
    LONGG[x] = deep_x;
    viz[x] = 1;
    oComponenta.push(x);
    for (int i = 0; i < G[x].size(); ++i) {
        if (!nivmax[G[x][i]]) {
            tarjan(G[x][i]);
            LONGG[x] = min(LONGG[x], LONGG[G[x][i]]);

        }
        else
        if (viz[G[x][i]]) {
            LONGG[x] = min(LONGG[x], LONGG[G[x][i]]);
        }
    }
    if (nivmax[x] == LONGG[x]) {
        int vf;
        ++NR;
        do {
            vf = oComponenta.top();
            oComponenta.pop();
            viz[vf] = 0;
            ctc[NR].push_back(vf);
        }while (vf != x);
    }
}

int main ()
{
    f>>n>> m;
    int x, y;
    for (int i = 1; i <= m; ++i) {
        f >> x >> y;
        G[x].push_back(y);
    }
    for (int i = 1; i <= n; ++i) {
        if (!nivmax[i]) {
            tarjan(i);
        }
    }
    g<<NR<<endl;
    for (int i=NR; i>= 1; --i) {
        for (int j=ctc[i].size() - 1; j>= 0; --j) {
            g <<ctc[i][j] << " ";
        }
        g << endl;
    }


    f.close();
    g.close();
    return 0;
}