Cod sursa(job #2367800)

Utilizator AlexToveAlexandru Toader AlexTove Data 5 martie 2019 12:18:44
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>

using namespace std;

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

int ad[105][105], adt[105][105], ans[105][105], viz1[105], viz2[105], cnt, cnt2, v[105], cnt3, p, q;
int n, m, x, y;

void dfs1(int nod)
{
    viz1[nod] = 1;
    for (int i = 1; i <= n; i++)
        if (!viz1[i] && ad[nod][i] == 1)
            dfs1(i);
    v[++cnt2] = nod;
}

void dfs2(int nod)
{
    viz2[nod] = cnt;
    ans[cnt][++ans[cnt][0]] = nod;
    for (int i = 0; i <= n; i++)
        if (!viz2[i] && adt[nod][i] == 1)
            dfs2(i);
}

void solve()
{
    for (int i = 1; i <= n; i++)
        if (!viz1[i])
            dfs1(i);

    for (int i=cnt2; i>=1; i--)
        if (!viz2[v[i]]) {
            cnt++;
            cnt3++;
            dfs2(v[i]);
        }
}

void show()
{
    cout<<cnt<<'\n';
    for(int i=1; i<=cnt; i++)
    {
        for(int j=1; j<= ans[i][0]; j++)
            cout<<ans[i][j]<<" ";
        cout<<'\n';
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        cin>>x>>y;
        ad[x][y] = 1;
        adt[y][x] = 1;
    }
    solve();
    show();
    return 0;
}