Cod sursa(job #3271058)

Utilizator Shaan_StefanShaan Stefan Shaan_Stefan Data 25 ianuarie 2025 09:50:32
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

#define NMAX 100000

using namespace std;
int n, m, x, y;
bool vis1[NMAX + 2], vis2[NMAX + 2];
int k = 0;

vector<int> ade[NMAX + 2], adi[NMAX + 2];
vector<int> af[NMAX + 2];
stack<int> kst;


void bfs1(int v)
{
    vis1[v] = 1;
    bool ok = 0;
    for(auto i : ade[v])
    {
        if(vis1[i] == 0)
        {
            ok = 1;
            bfs1(i);
        }
    }
    if(!ok)
        kst.push(v);
}

void bfs2(int v)
{
    vis2[v] = 1;
    af[k].push_back(v);
    for(auto i : adi[v])
    {
        if(vis2[i] == 0)
            bfs2(i);   
    }
}
int main()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);

    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++)
    {
        scanf("%d %d", &x, &y);
        ade[x].push_back(y);
        adi[y].push_back(x);
    };

    for(int i = 1; i <= n; i++)
    {
        if(vis1[i] == 0)
            bfs1(i);
    }
    while(!kst.empty())
    {
        int tp = kst.top();
        kst.pop();
        if(vis2[tp] == 0)
        {
            k++;
            bfs2(tp);
        }
    }

    printf("%d\n", k);
    for(int i = 1; i <= k; i++)
    {
        sort(af[i].begin(), af[i].end());
        for(auto j : af[i])
        {
            printf("%d ", j);
        }
        printf("\n");
    }
    return 0;
}