Cod sursa(job #2978104)

Utilizator maiaauUngureanu Maia maiaau Data 12 februarie 2023 22:58:00
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>
using namespace std;

#define pb push_back

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

const int N = 1e5 + 5;

int n, k, used, u[N];
vector<int> G[N], GT[N], ctc[N];
stack<int> s;

void read(), dfs(int), dfsGT(int);

int main()
{
    read();
    for (int i = 1; i <= n; i++)
        if (!u[i]) dfs(i);
    memset(u, 0, sizeof u);
    while (used != n){
        while (u[s.top()]) s.pop();
        k++; dfsGT(s.top());
        s.pop();
    }
    g << k << '\n';
    for (int i = 1; i <= k; i++){
        for (auto it: ctc[i]) g << it << ' ';
        g << '\n';
    }

    return 0;
}

void read(){
    int m, a, b;
    f >> n >> m;
    for (; m; m--){
        f >> a >> b;
        G[a].pb(b); GT[b].pb(a);
    }
}

void dfs(int nod){
    u[nod] = 1;
    for (auto it: G[nod])
        if (!u[it])
            dfs(it);
    s.push(nod);
}

void dfsGT(int nod){
    u[nod] = 1; used++;
    ctc[k].pb(nod);
    for (auto it: GT[nod])
        if (!u[it])
            dfsGT(it);
}