Cod sursa(job #3030841)

Utilizator maiaauUngureanu Maia maiaau Data 17 martie 2023 22:13:38
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 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, viz, k;
bitset<N> u;
vector<int> G[N], GT[N];
vector<vector<int>> CTC;
stack<int> stk;

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

int main()
{
    read();
    for (int i = 1; i <= n; i++)
        if (!u[i]) dfs(i);
    u.reset();
    while (viz != n){
        CTC.pb({}); 
        while (u[stk.top()]) stk.pop();
        dfsGT(stk.top()); stk.pop();
        k++;
    }
    g << CTC.size() << '\n';
    for (auto i: CTC){
        for (auto j: i)
            g << j << ' ';
        g << '\n';
    } 
    
    return 0;
}

void read() {
    int m, x, y;
    f >> n >> m;
    for (; m; m--){
        f >> x >> y;
        G[x].pb(y);
        GT[y].pb(x);
    }
}
void dfs(int nod){
    u[nod] = 1; 
    for (auto it: G[nod])
        if (!u[it]) dfs(it);
    stk.push(nod);
}
void dfsGT(int nod){
    u[nod] = 1; viz++;
    CTC[k].pb(nod);
    for (auto it: GT[nod])
        if (!u[it]) dfsGT(it);
}