Cod sursa(job #744075)

Utilizator memaxMaxim Smith memax Data 7 mai 2012 12:29:35
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

int n,m;
vector< vector<int> > g(1), u(1);
vector<int> q, c(1), y;
ofstream cour ("ctc.out");

void de(int k);
void det(int k);

int main(){
    ifstream cinr ("ctc.in");
    int a,b;
    cinr >> n;
    cinr >> m;
    for(int i=1; i<=n; i++){
            g.push_back(vector<int>() );
            u.push_back(vector<int>() );
            c.push_back(0);
            }
    for(int i=1; i<=m; i++){
            cinr >> a;
            cinr >> b;
            g[a].push_back(b);
            u[b].push_back(a);
            }
    for(int i=1; i<=n; i++){
            if(c[i]==0){
                        de(i);
                        }
            }
    for(int i=1; i<=n; i++){c[i]=0;}
    a=0;
    for(int i=1; i<=n; i++){
            if(c[q.back()]==0){ 
                                a++;
                                y.push_back(0);
                                det(i); }
            q.pop_back();
            }
    cour << a << "\n";
    while(!y.empty()){
                      if(y.back()==0){
                                      cour << "\n";
                                      }else {
                                            cour << y.back() <<  " ";
                                            }
                      y.pop_back();
                      }
    //cin.ignore(2);
    return 0;
    }
    
void det(int k){
     c[k]=1;
     for(int i=0; i<u[k].size(); i++){
             if(c[u[k][i]]==0){
                               det(u[k][i]);
                               }
             }
     c[k]=2;
     y.push_back(k);
     }
    
void de(int k){
     c[k]=1;
     for(int i=0; i<g[k].size(); i++){
             if(c[g[k][i]]==0){
                               de(g[k][i]);
                               }
             }
     c[k]=2;
     q.push_back(k);
     }