Cod sursa(job #3212428)

Utilizator maiaauUngureanu Maia maiaau Data 11 martie 2024 18:39:22
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
#define pb push_back

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

const int N = 1e5+3;

int n, k;
bitset<N> u;
stack<int> stk;
vector<vector<int>> g, gt, comp;

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

int main()
{
    read();
    for (int i = 1; i <= n; i++)
        if (!u[i])
            dfs(i);
    u.reset();
    while (!stk.empty()){
        int nod = stk.top(); stk.pop();
        if (u[nod]) continue;
        comp.pb({});
        dfsgt(nod);
        k++;
    }
    fout << k;
    for (int i = 0; i < k; i++) {
        fout << '\n';
        for (auto it: comp[i]) fout << it << ' ';
    }
    
    return 0;
}

void read(){
    int m; fin >> n >> m;
    g.resize(n+3); gt.resize(n+3);
    while (m--){
        int a, b; fin >> 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);
    stk.push(nod);
}
void dfsgt(int nod){
    comp[k].pb(nod);
    u[nod] = 1;
    for (auto it: gt[nod]) 
        if (!u[it])
            dfsgt(it);
}