Cod sursa(job #2341601)

Utilizator atatomirTatomir Alex atatomir Data 11 februarie 2019 23:44:55
Problema Componente tare conexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

//#define debug(x) ;
#define debug(x) cerr << #x << " = " << x << "\n";

ostream& operator<<(ostream& cerr, vector<ll> aux) {
    cerr << "[";
    for (auto e : aux) cerr << e << ' ';
    cerr << "]";
    return cerr;
}

const int maxN = 100011;

int n, m, i, x, y;
vector<int> list[maxN];
bool us[maxN];
vector<int> ord, here, aux;
vector< vector<int> > ans;

void dfs(int node) {
    us[node] = true;
    here.pb(node);
    for (auto to : list[node])
        if (!us[to])
            dfs(to);
    ord.pb(node);
}

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

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

    for (i = 1; i <= n; i++)
        if (!us[i])
            dfs(i);
    
    memset(us, 0, sizeof(us));
    aux = ord;
    for (auto e : aux) {
        if (us[e]) continue;
        here.clear();
        dfs(e);
        ans.pb(here);
    }

    printf("%d\n", ans.size());
    for (auto v: ans) {
        for (auto e : v) printf("%d ", e);
        printf("\n");
    }


    return 0;
}