Cod sursa(job #1082320)

Utilizator beldeabogdanBogdan Beldea beldeabogdan Data 14 ianuarie 2014 14:46:05
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;

vector <int> g[100005];
vector <int> gt[100005];
vector <int> r[100005];
vector <int> :: iterator it;
bool viz[100005];
stack <int> stk;
int n,m,nr;

void create(int s) {
    vector <int> :: iterator it;
    viz[s] = true;
    for (it = g[s].begin();it!=g[s].end();it++) if (!viz[*it]) create(*it);
    stk.push(s);
}

void dfs(int s) {
    vector <int> :: iterator it;
    viz[s] = false;
    for (it = gt[s].begin();it!=gt[s].end();it++) if (viz[*it]) dfs(*it);
    r[nr].push_back(s);
}

int main() {
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d %d",&n,&m);
    for (int i=1;i<=m;i++) {
        int a,b;
        scanf("%d %d",&a,&b);
        g[a].push_back(b);
        gt[b].push_back(a);
    }
    for (int i=1;i<=n;i++) if (!viz[i]) create(i);
    while (!stk.empty()) {
        int s = stk.top(); stk.pop();
        if (viz[s]) {
            dfs(s);
            nr++;
        }
    }
    printf("%d\n",nr);
    while (nr--) {
        for (it = r[nr].begin();it!=r[nr].end();it++)
            printf("%d ",*it);
        printf("\n");
    }
    return 0;
}