Cod sursa(job #1097707)

Utilizator StexanIarca Stefan Stexan Data 3 februarie 2014 21:06:15
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
//
//  main.cpp
//  Componente tare conexe
//
//  Created by Stefan Iarca on 2/3/14.
//  Copyright (c) 2014 Stefan Iarca. All rights reserved.
//

#include <fstream>
#include <vector>
using namespace std;

#define NMAX 100010

ifstream f("ctc.in");
ofstream g("ctc.out");

vector<int> G[NMAX], Gt[NMAX],Cicluri[NMAX];
bool Used[NMAX];
int N,M,O[NMAX],k,Count;

void Read(){
    f>>N>>M; int x,y;
    for (int i = 1; i <= M; i++) {
        f>>x>>y;
        G[x].push_back(y);
        Gt[y].push_back(x);
    }
    
}

void DFS(int Node){
    Used[Node] = true;
    for (vector<int>::iterator it = G[Node].begin(); it < G[Node].end(); it++) {
        if (!Used[*it]) {
            DFS(*it);
        }
    }
    O[++k] = Node;
}

void DFSt(int Node){
    Used[Node] = true;
    Cicluri[Count].push_back(Node);
    for (vector<int>::iterator it = Gt[Node].begin(); it < Gt[Node].end(); it++) {
        if (!Used[*it]) {
            DFSt(*it);
        }
    }
}

void Solve(){
    for (int i = 1; i <= N; i++) {
        if(!Used[i]){
            DFS(i);
        }
    }
    for (int i = 0; i <= N; i++) {
        Used[i] = false;
    }
    for (int i = k; i > 0 ; i--) {
        if(!Used[O[i]]){
            Count++;
            DFSt(O[i]);
        }
    }

}
void Write(){
    g<<Count<<"\n";
    for (int i = 1; i <= Count; i++) {
        for (vector<int>::iterator it = Cicluri[i].begin(); it < Cicluri[i].end(); it++) {
            g<<*it<<" ";
        }
        g<<"\n";
    }
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}