Cod sursa(job #3371087)

Utilizator natalia_denisa14Natalia natalia_denisa14 Data 28 octombrie 2026 16:34:24
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>
#define nmax 100005
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");

vector<int> adj[nmax],gt[nmax],cc[nmax];
stack <int> s;
int st,dr,n,m,nr_cc;
int viz[nmax];
void dfs(int nod) {
    viz[nod]=1;
    s.push(nod);
    for (int j=0;j<adj[nod].size();j++)
        if (!viz[adj[nod][j]]) dfs(adj[nod][j]);
}
void dfs_gt(int nod, int cnt) {
    cc[cnt-1].push_back(nod);
    viz[nod]=2;
    for (int j=0;j<gt[nod].size();j++) {
        if (viz[gt[nod][j]]==1) dfs_gt(gt[nod][j],cnt);
    }
}
int main() {
    f>>n>>m;

    for (int i=1;i<=m;i++) {
        f>>st>>dr;
        adj[st].push_back(dr);
        gt[dr].push_back(st);
    }

    for (int i=1;i<=n;i++) if (!viz[i]) dfs(i);
    while (s.size()) {
        int varf=s.top(); s.pop();
        if (viz[varf]==1) {
            nr_cc++; dfs_gt(varf,nr_cc);
        }
    }
    g<<nr_cc<<'\n';
    for (int i=0;i<nr_cc;i++) {
        for (int j=0;j<cc[i].size();j++)
            g<<cc[i][j]<<' ';
        g<<'\n';
    }
    return 0;
}