Cod sursa(job #2500946)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 28 noiembrie 2019 21:20:44
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.39 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];

bool Sel[NMAX], Sel1[NMAX], Sel2[NMAX];;
int Elem, V[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)
{
    Sel1[Node] = 1;

    V[++Elem] = Node;

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

    return;
}

static inline void DFS2 (int Node)
{
    Sel2[Node] = 1;

    if(!Sel1[Node])
        V[++Elem] = Node;

    for(auto it : T[Node])
        if(!Sel2[it])
            DFS2(it);

    return;
}

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

            Elem = 0;

            DFS1(i);
            DFS2(i);

            for(int j = 1; j <= Elem; ++j)
                if(Sel1[V[j]] && Sel2[V[j]])
                {
                    Sel[V[j]] = 1;

                    Sol[cnt].push_back(V[j]);
                }
                else
                    Sel1[V[j]] = Sel2[V[j]] = 0;
        }

    return;
}

static inline void Write ()
{
    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;
}