Cod sursa(job #990065)

Utilizator florin.elfusFlorin Elfus florin.elfus Data 27 august 2013 12:53:13
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.94 kb
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>

#define REP(i, a, b) for(int i = a; i <= b; ++i)
#define REPD(i, a, b) for(int i = a; i >= b; --i)
#define FOR(i, n) REP(i, 1, n)
#define FOREACH(it, G) for(__typeof(G.begin()) it = G.begin() ; it != G.end() ; ++ it)
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define read(n) int (n); scanf("%d", &(n))
#define read2(n, m) int (n), (m); scanf("%d %d", &(n), &(m))
#define read3(n, m, k) int (n), (m), (k); scanf("%d %d %d", &(n), &(m), &(k))
#define ll long long
#define x first
#define y second
#define mp make_pair
#define pb push_back

using namespace std;

vector <int> G[160000], GT[160000];
bool vis[160000];
int stk[160000];

void dfs1(int nod) {
    vis[nod] = 1;
    FOREACH(it, GT[nod])
        if (!vis[*it])
            dfs1(*it);
    stk[++stk[0]] = nod;
}

vector <int> scc[160000];
int which[160000];

void dfs2(int nod, int tmp) {
    scc[tmp].pb(nod);
    vis[nod] = 1;
    FOREACH(it, G[nod])
        if (!vis[*it])
            dfs2(*it, tmp);
}

int sccCnt = 0;

void makeDag(int n) {
    FOR(i, n)
        if (!vis[i])
            dfs1(i);
    FOR(i, n)
        vis[i] = 0;
    int tmp = 0;
    REPD(i, stk[0], 1)
        if (!vis[stk[i]]) {
            ++tmp;
            dfs2(stk[i], tmp);
        }
    sccCnt = tmp;
}

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

    read2(n, m);
    FOR(i, m) {
        read2(X0, Y0);
        G[X0].pb(Y0);
        GT[Y0].pb(X0);
    }

    makeDag(n);
    printf("%d\n", sccCnt);
    FOR(i, sccCnt) {
        FOREACH(it, scc[i])
            printf("%d ", *it);
        printf("\n");
    }

    return 0;
}