Cod sursa(job #3349143)

Utilizator mateispnSpinu Matei mateispn Data 25 martie 2026 17:43:01
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
using namespace std;

int G[2][10001][10001];
int n, m;

int V[100001], M[100001], nrc, k, o[100001];

ifstream cin("ctc.in");
ofstream cout("ctc.out");

void dfs1(int vf) {
    V[vf] = 1;
    for(int i = 1; i <= n; i ++)
        if(!V[i] && G[0][vf][i]) {
            dfs1(i);
        }
        o[++k]=vf;
}
void dfs2(int vf) {
    M[vf] = nrc;
    for(int i = 1; i <= n; i ++)
        if(!M[i] && G[1][vf][i]) {
            dfs2(i);
        }
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i ++) {
        int a, b;
        cin >> a >> b;
        G[0][a][b] = G[1][b][a] = 1;
    }

    for(int i = 1;i <= n; i ++)
        if(!V[i]) dfs1(i);

    for(int i = k;i >= 1; i --)
        if(!M[o[i]])
    {
        nrc++;
        dfs2(o[i]);
    }

    cout<<nrc<<'\n';

    for(int i = 1;i <= nrc; i ++, cout<<'\n')
        for(int j = 1;j <= n; j ++)
           if(M[j]==i) cout<<j<<' ';

    return 0;
}