Cod sursa(job #1707069)

Utilizator Theodor1000Cristea Theodor Stefan Theodor1000 Data 24 mai 2016 09:29:08
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>

using namespace std;

vector <int> v[100010], iv[100010];
stack <int> st, cst;
bool ap[100010];

inline void dfs (int nod)
{
    ap[nod] = true;

    for (auto &it : v[nod])
        if (!ap[it]) dfs (it);

    st.push (nod);
    cst.push (nod);
}

inline void df (int nod, bool OK)
{
    if (OK) printf ("%d ", nod);
    ap[nod] = true;

    for (auto &it : iv[nod])
        if (!ap[it]) df (it, OK);
}

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

    int n, m;
    scanf ("%d %d", &n, &m);

    for (int i = 1; i <= m; ++i)
    {
        int x, y;
        scanf ("%d %d", &x, &y);

        v[x].push_back (y);
        iv[y].push_back (x);
    }

    for (int i = 1; i <= n; ++i)
        if (!ap[i]) dfs (i);

    memset (ap, false, sizeof (ap));

    int nr = 0;
    while (!st.empty ())
    {
        int x = st.top ();
        st.pop ();

        if (!ap[x]) df (x, false), ++nr;
    }

    st.swap (cst);

    memset (ap, false, sizeof (ap));

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

    while (!st.empty ())
    {
        int x = st.top ();
        st.pop ();

        if (!ap[x])
        {
            df (x, true);
            printf ("\n");
        }
    }

    return 0;
}