Cod sursa(job #1810666)

Utilizator serbanSlincu Serban serban Data 20 noiembrie 2016 14:01:38
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <stack>
#include <fstream>
#include <vector>

using namespace std;

vector<int> L[100005];
vector<int> G[100005];

int ind[100005];
int low[100005];
int cur;

stack<int> S;

int k;
vector<int> sol[100005];

void tarjan(int x) {

    S.push(x);

    cur ++;
    ind[x] = low[x] = cur;
    for(int i = 0; i < L[x].size(); i ++) {
        if(!ind[L[x][i]])
            tarjan(L[x][i]);
        low[x] = min(low[x], low[L[x][i]]);
    }
    if(ind[x] == low[x]) {
        k ++;

        int nod;
        do {
            nod = S.top();
            S.pop();
            sol[k].push_back(nod);
        }
        while(nod != x);
    }
}

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

    int n, m, x, y;
    f >> n >> m;
    for(int i = 1; i <= m; i ++) {
        f >> x >> y;
        L[x].push_back(y);
        G[y].push_back(x);
    }

    for(int i = 1; i <= n; i ++) {
        if(ind[i] == 0)
            tarjan(i);
    }

    g << k << "\n";
    for(int i = 1; i <= k; i ++) {
        for(int j = 0; j < sol[i].size(); j ++)
            g << sol[i][j] << " ";
        g << "\n";
    }
    return 0;
}