Cod sursa(job #2971503)

Utilizator Theodor17Pirnog Theodor Ioan Theodor17 Data 27 ianuarie 2023 15:05:14
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
#include <bitset>

using namespace std;

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

const int NMAX = 1e5;

vector <int> g[NMAX + 1], rg[NMAX + 1], ans[NMAX + 1];
bitset <NMAX + 1> viz;
stack <int> stiva;
int ctc;

void dfs(int x){

    viz[x] = 1;

    for(auto y : g[x])
        if(!viz[y])
            dfs(y);

    stiva.push(x);

}

void dfs2(int x){

    viz[x] = 1;
    ans[ctc].push_back(x);

    for(auto y : rg[x])
        if(!viz[y])
            dfs2(y);

}

int main(){

    int n = 0, m = 0;
    cin >> n >> m;

    for(int i = 0; i < m; i++){

        int x = 0, y = 0;
        cin >> x >> y;

        g[x].push_back(y);
        rg[y].push_back(x);

    }

    for(int i = 1; i <= n; i++)
        if(!viz[i])
            dfs(i);
        
    viz = 0;

    while(!stiva.empty()){

        if(viz[stiva.top()]){

            stiva.pop();
            continue;

        }

        ctc++;
        dfs2(stiva.top());
        stiva.pop();

    }

    cout << ctc << "\n";
    for(int i = 1; i <= ctc; i++){

        sort(ans[i].begin(), ans[i].end());
        for(auto y : ans[i])
            cout << y << " ";


        cout << "\n";

    }

}