Cod sursa(job #3277509)

Utilizator andiRTanasescu Andrei-Rares andiR Data 16 februarie 2025 14:50:27
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <iomanip>
#include <vector>

#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front

using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
typedef long long ll;
const ll Nmax=1e5+5, inf=1e9+5;
using pll=pair<ll, ll>;

int n, m, nrtc, crt;
int ord[Nmax];
bool vis[Nmax];
vector <int> ad[Nmax], adc[Nmax], tc[Nmax];
void dfs1 (int nod){
    vis[nod]=1;
    for (auto it:ad[nod])
        if (!vis[it])
            dfs1(it);
    ord[crt++]=nod;
}
void dfs2 (int nod){
    vis[nod]=1;
    tc[nrtc].pb(nod+1);
    for (auto it:adc[nod])
        if (!vis[it])
            dfs2(it);
}
inline void Kosaraju(){
    for (int i=0; i<n; i++)
        if (!vis[i])
            dfs1(i);
    for (int i=0; i<n; i++)
        vis[i]=0;
    for (int i=n-1; i>=0; i--)
        if (!vis[ord[i]]){
            dfs2(ord[i]);
            nrtc++;
        }
}
inline void Afisare(){
    fout<<nrtc<<'\n';
    for (int i=0; i<nrtc; i++){
        for (auto it:tc[i])
            fout<<it<<' ';
        fout<<'\n';
    }
}
int main()
{
    fin>>n>>m;
    int a, b;
    for (int i=0; i<m; i++){
        fin>>a>>b;
        a--; b--;
        ad[a].pb(b);
        adc[b].pb(a);
    }
    Kosaraju();
    Afisare();
    return 0;
}