Cod sursa(job #2447524)

Utilizator bluestorm57Vasile T bluestorm57 Data 13 august 2019 15:39:10
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 100005;
int n,m,ans,where[NMAX];
vector <int> vo[NMAX], vi[NMAX], discovered, G[NMAX];
bool used[NMAX];

void DFP(int node){
    used[node] = 1;
    for(auto it: vo[node])
        if(!used[it])
            DFP(it);
    discovered.push_back(node);
}

void DFM(int node, int which){
    where[node] = which;
    G[which].push_back(node);
    for(auto it: vi[node])
        if(!where[it])
            DFM(it, which);

}

int main(){
    int i,x,y;
    f >> n >> m;
    for(i = 1 ; i <= m ; i++){
        f >> x >> y;
        vo[x].push_back(y);
        vi[y].push_back(x);
    }

    for(i = 1 ; i <= n ; i++)
        if(!used[i])
            DFP(i);

    while(!discovered.empty()){
       if(!where[discovered.back()]){
            ans++;
            DFM(discovered.back(), ans);
        }
        discovered.pop_back();
    }

    g << ans << "\n";
    for(i = 1 ; i <= ans ; i++){
        for(auto it : G[i])
            g << it << " " ;
        g << "\n";
    }
    return 0;
}