Cod sursa(job #3360372)

Utilizator mtcmtcmtc mtc mtcmtc Data 13 iulie 2026 12:31:13
Problema Componente tare conexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
const int maxn=100005;
vector<int>adj[maxn];
vector<int>inv[maxn];
vector<int>ctc[maxn];
int nr;
bool vis[maxn];
int v[maxn],k;
void sort(int nod){
    vis[nod]=1;
    for(auto e:adj[nod]){
        if(vis[e]==0) sort(e);
    }
    v[++k]=nod;
}
void dfs(int nod){
    vis[nod]=1;
    for(auto e:adj[nod]){
        if(vis[e]==0) ctc[nr].push_back(e),dfs(e);
    }
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        inv[b].push_back(a);
    }
    for(int i=1;i<=n;i++){
        if(vis[i]==0) sort(i);
    }
    for(int i=1;i<=n;i++){
        vis[i]=0;
    }
    for(int i=1;i<=n;i++){
        if(vis[v[i]]==0) ctc[++nr].push_back(v[i]),dfs(v[i]);
    }
    cout<<nr<<'\n';
    for(int i=1;i<=nr;i++){
        for(auto e:ctc[i]){
            cout<<e<<" ";
        }
        cout<<'\n';
    }
    return 0;
}