Cod sursa(job #1920061)

Utilizator blatulInstitutul de Arta Gastronomica blatul Data 9 martie 2017 22:18:23
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 100000;

vector<int> G[kMaxN];
int Idx[kMaxN], ST[kMaxN];
bool OnStack[kMaxN];

vector<int> CTC[kMaxN];
int numCtc;

int Tarjan(int node) {
    static int freeIdx = 0, stkSize = 0;
    int minPtr = Idx[node] = ++freeIdx;
    
    ST[stkSize++] = node;
    OnStack[node] = true;
    for(const int& son : G[node])
        if(!Idx[son])
            minPtr = min(minPtr, Tarjan(son));
        else if(OnStack[son]) 
            minPtr = min(minPtr, Idx[son]);
        
    if(Idx[node] == minPtr) {
        int aux;
        do {
            aux = ST[--stkSize];
            OnStack[aux] = false;
            CTC[numCtc].push_back(aux);
        } while(aux != node);
        numCtc++;
    }
    return minPtr;
}

int main() {
    #ifdef INFOARENA
    ifstream cin("ctc.in");
    ofstream cout("ctc.out");
    #endif
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    int n, m;
    cin >> n >> m;
    
    for(int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        G[x - 1].push_back(y - 1);
    }
    
    for(int i = 0; i < n; ++i)
        if(!Idx[i])
            Tarjan(i);
            
            
    cout << numCtc << '\n';
    for(int i = 0; i < numCtc; ++i) {
        for(const int& nodes: CTC[i])
            cout << nodes + 1 << ' ';
        cout << '\n';
    }
}