Cod sursa(job #1687423)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 12 aprilie 2016 20:59:55
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e5 + 10;

int n , m , i , nrc;
bool used[nmax];

vector < int > v;
vector < int > g[nmax] , gt[nmax] , ssc[nmax];

void dfs(int node)
{
    used[node] = 1;
    for (auto &it : g[node])
    {
        if (used[it]) continue;
        dfs(it);
    }
    v.push_back(node);
}

void dfsT(int node)
{
    used[node] = 0;
    ssc[nrc].push_back(node);

    for (auto &it : gt[node])
    {
        if (!used[it]) continue;
        dfsT(it);
    }
}

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

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

    for (i = 1; i <= n; ++i)
    {
        if (used[i]) continue;
        dfs(i);
    }

    for ( ; v.size(); v.pop_back())
    {
        int node = v.back();

        if (!used[node]) continue;
        ++nrc; dfsT(node);
    }

    printf("%d\n", nrc);
    for (i = 1; i <= nrc; ++i, printf("\n"))
        for (auto &it : ssc[i])
            printf("%d ", it);

    return 0;
}