Cod sursa(job #586665)

Utilizator palcuiealexAlex Palcuie palcuiealex Data 2 mai 2011 18:32:07
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int MAX_NODURI = 100004;
int nNoduri, nMuchii;
vector<int> grafNormal[MAX_NODURI], grafTranspus[MAX_NODURI];
vector< vector<int> > solution;
int used[MAX_NODURI];

void read_input(){
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);


    scanf("%d%d",&nNoduri,&nMuchii);
    for (int i=0; i<nMuchii; ++i){
        static int x, y;
        scanf("%d%d",&x,&y);
        grafNormal[x].push_back(y);
        grafTranspus[y].push_back(x);
    }
}


void dfs (const int nod, vector<int>* graf, int step){
    vector<int>::iterator it;
    used[nod] = step;
    if (step == 2)
        solution[solution.size()-1].push_back(nod);
    for(it = graf[nod].begin(); it != graf[nod].end(); ++it){
        if (used[*it] == step-1)
            dfs(*it,graf,step);
    }
}


void solve(){
    vector<int> emptyVector;
    for (int i=1; i<=nNoduri; ++i){
        if (used[i]!=2){
            solution.push_back(emptyVector);
            dfs(i,grafNormal, 1);
            dfs(i,grafTranspus, 2);
        }
    }
}


void  print_output(){
    printf("%d\n",solution.size());
    for (int i=0; i<solution.size(); ++i){
        for(int j=0; j<solution[i].size(); ++j)
            printf("%d ",solution[i][j]);
        printf("\n");
    }
}


int main()
{
    read_input();
    solve();
    print_output();
    return 0;
}