Cod sursa(job #1480467)

Utilizator retrogradLucian Bicsi retrograd Data 2 septembrie 2015 17:15:54
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>

using namespace std;

#define MAXN 100005

vector<int> G[MAXN], Gt[MAXN];
bitset<MAXN> Viz1, Viz2;

void dfs(int node, vector<int> G[], bitset<MAXN> &Viz) {
    Viz[node] = 1;
    for(auto vec : G[node])
        if(!Viz[vec])
            dfs(vec, G, Viz);
}

int In[MAXN];
vector<int> Nodes[MAXN];


int main() {

    //#ifndef ONLINE_JUDGE
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    //#endif

    int n, m, a, b;
    cin>>n>>m;

    while(m--) {
        cin>>a>>b;
        G[a].push_back(b);
        Gt[b].push_back(a);
    }

    int ctc = 0;
    for(int i=1; i<=n; i++) {
        if(!In[i]) {
            ctc++;

            dfs(i, G, Viz1);
            dfs(i, Gt, Viz2);

            for(int j=1; j<=n; j++) {
                if(Viz1[j] && Viz2[j]) {
                    In[j] = ctc;
                    Nodes[ctc].push_back(j);
                }
            }

            Viz1.reset();
            Viz2.reset();

        }
    }

    cout<<ctc<<'\n';
    for(int i=1; i<=ctc; i++) {
        for(auto node : Nodes[i]) cout<<node<<" ";
        cout<<'\n';
    }

    return 0;
}