Cod sursa(job #1483203)

Utilizator tiby10Tibi P tiby10 Data 8 septembrie 2015 22:16:18
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bitset>
#include <vector>
#include <iostream>
#include <cstdio>

using namespace std;

#define MAXN 100005

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


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

void dfs1(int node) {
    Viz1[node] = ctc;
    for(auto vec : G[node])
        if(Viz1[vec] < ctc && In[vec] == 0)
            dfs1(vec);
}

void dfs2(int node) {
    if(Viz1[node] == ctc) {
        In[node] = ctc;
        Nodes[ctc].push_back(node);
    }

    Viz2[node] = ctc;
    for(auto vec : Gt[node])
        if(Viz2[vec] < ctc && In[vec] == 0)
            dfs2(vec);
}



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);
    }

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

            dfs1(i);
            dfs2(i);
        }
    }

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

    return 0;
}