Cod sursa(job #2500971)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 28 noiembrie 2019 21:45:32
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.27 kb
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int BSIZE = (1 << 16), NMAX = 1e5 + 5;

int N, M, x, y, cnt = 0;

vector < int > G[NMAX], T[NMAX];
vector < int > V;

bool Sel[NMAX];
int Where[NMAX];

vector < int > Sol[NMAX];

///
int pos = BSIZE - 1;
char buff[BSIZE];

static inline char Char ()
{
    ++pos;

    if(pos == BSIZE)
    {
        pos = 0;

        fread(buff, 1, BSIZE, stdin);
    }

    return buff[pos];
}

static inline int Int ()
{
    int r = 0;

    for(;;)
    {
        char ch = Char();

        if(isdigit(ch))
        {
            r = (ch - '0');

            break;
        }
    }

    for(;;)
    {
        char ch = Char();

        if(isdigit(ch))
            r = r * 10 + (ch - '0');
        else
            break;
    }

    return r;
}
///

static inline void Read ()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);

    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);

    N = Int();
    M = Int();

    for(int i = 1; i <= M; ++i)
    {
        x = Int();
        y = Int();

        G[x].push_back(y);
        T[y].push_back(x);
    }

    return;
}

static inline void DFS1 (int Node)
{
    Sel[Node] = 1;

    for(auto it : G[Node])
        if(!Sel[it])
            DFS1(it);

    V.push_back(Node);


    return;
}

static inline void DFS2 (int Node, int ord)
{
    Where[Node] = ord;

    for(auto it : T[Node])
        if(!Where[it])
            DFS2(it, ord);

    return;
}

static inline void Solve ()
{
    for(int i = 1; i <= N; ++i)
        if(!Sel[i])
            DFS1(i);

    for(int i = (int)V.size() - 1; i >= 0; --i)
        if(!Where[V[i]])
        {
            ++cnt;

            DFS2(V[i], cnt);
        }

    return;
}

static inline void Load ()
{
    for(int i = 1; i <= N; ++i)
        Sol[Where[i]].push_back(i);

    return;
}

static inline void Write ()
{
    Load();

    printf("%d\n", cnt);

    for(int i = 1; i <= cnt; ++i)
    {
        for(auto it : Sol[i])
            printf("%d ", it);

        printf("\n");
    }

    return;
}

int main()
{
    Read();

    Solve();

    Write();

    return 0;
}