Cod sursa(job #824699)

Utilizator codename47Codename 47 codename47 Data 26 noiembrie 2012 21:10:57
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <cstring>
#define NMAX 100001

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int N, M, K;
int S[NMAX];
int U[NMAX];

struct list {
    int inf;
    list *next;
};

list *G[NMAX];
list *GT[NMAX];

void add(int a, int b, int arg) {
    list *q = new list;
    q->inf = b;
    if(!arg) {
        q->next = G[a];
        G[a] = q;
    } else {
        q->next = GT[a];
        GT[a] = q;
    }
}

void read() {
    int i, a, b;
    fin >> N >> M;
    for(i = 1; i <= M; ++i) {
        fin >> a >> b;
        add(a, b, 0);
        add(b, a, 1);
    }
}

void dfs(int nod) {
    list *it;
    U[nod] = 1;
    for(it = G[nod]; it; it = it->next)
        if(!U[it->inf])
            dfs(it->inf);
    S[++K] = nod;
}

void dfsT(int nod, int arg) {
    list *it;
    U[nod] = 1;
    if(arg) fout << nod << ' ';
    for(it = GT[nod]; it; it = it->next)
        if(!U[it->inf])
            dfsT(it->inf, arg);
}

void solve() {
    int i, count = 0;
    for(i = 1; i <= N; ++ i)
        if(!U[i]) dfs(i);
    memset(U, 0, sizeof(U));
    for(i = K; i >= 1; --i)
        if(!U[S[i]]) {
            ++count;
            dfsT(S[i], 0);
        }
    fout << count << '\n';
    memset(U, 0, sizeof(U));
    for(i = K; i >= 1; -- i)
        if(!U[S[i]]) {
            dfsT(S[i], 1);
            fout << '\n';
        }
}

int main() {
    read();
    solve();
    return 0;
}