Cod sursa(job #1964776)

Utilizator RaZxKiDDavid Razvan RaZxKiD Data 13 aprilie 2017 17:46:38
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

ifstream in("ctc.in");
ofstream out("ctc.out");

int n,m;
vector<int> L[100005];
vector<int> LT[100005];

int c;
bool U[100005];
vector<int> PO;
vector<int> C[100005];

void read(){
    in>>n>>m;
    for(int i=1,x,y;i<=m;i++){
        in>>x>>y;
        L[x].push_back(y);
        LT[y].push_back(x);
    }
}
void dfs(int nod){
    U[nod]=1;
    for(auto x : L[nod]){
        if(!U[x]){
            dfs(x);
        }
    }
    PO.push_back(nod);
}
void dfst(int nod){
    U[nod]=1;
    C[c].push_back(nod);
    for(auto x : LT[nod]){
        if(!U[x]){
            dfst(x);
        }
    }
}
void solve(){
    for(int i=1;i<=n;i++)
        if(!U[i])
            dfs(i);
    memset(U,0,sizeof(U));
    for(auto it=PO.rbegin();it!=PO.rend();it++){
        if(!U[*it])
            c++,
            dfst(*it);
    }
    out<<c<<"\n";
    for(int i=1;i<=c;i++){
        for(auto x : C[i])
            out<<x<<" ";
        out<<"\n";
    }
}
int main(){
    read();
    solve();
    return 0;
}