Cod sursa(job #1790727)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 28 octombrie 2016 17:33:51
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>

using namespace std;
int N,M;
const int Nmax = 666013;
vector<vector<int>> G, Gt, ctc;
vector<int> crt;
stack<int> S;
bitset<Nmax> used;


void DFS(int k)
{
    used[k] = 1;
    for(auto it : G[k])
        if(!used[it])
            DFS(it);
    S.push(k);
}

void DFST(int k)
{
    used[k] = 1;
    crt.push_back(k);
    for(auto it : Gt[k])
        if(!used[it])
            DFST(it);
}

int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);

    cin.sync_with_stdio(false);

    cin >> N >> M;
    G.resize(N+1);
    Gt.resize(N+1);

    for(int i = 1; i <= M; ++i) {
        int a,b;
        cin >> a >> b;
        G[a].push_back(b);
        Gt[b].push_back(a);
    }

    for(int i = 1; i <= N; ++i)
        if(!used[i])
            DFS(i);
    used = 0;

    while(!S.empty()) {
        int k = S.top(); S.pop();

        if(used[k])
            continue;
        DFST(k);
        ctc.push_back(crt);
        crt.clear();
    }

    cout << ctc.size() << "\n";
    for(auto it : ctc) {
        sort(it.begin(), it.end());
        for(auto jt : it)
            cout << jt << " ";
        cout << "\n";
    }

    return 0;
}