Cod sursa(job #766162)

Utilizator mi5humihai draghici mi5hu Data 10 iulie 2012 14:49:36
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.18 kb
#include <stdio.h>
#include <fstream>
#include <vector>
#include <stack>
#define NMAX 100001
using namespace std;

int n, m, ind = 1;

stack<int> S;
vector< vector<int> > rez;

vector<int> edges[NMAX];
int lowlink[NMAX];
int index[NMAX];
bool inStack[NMAX];


int min(int a, int b) {
    return a < b ? a : b;
}

void read_() {
    int source, dest;          
    ifstream fin("ctc.in");
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        fin >> source >> dest;
        edges[source].push_back(dest);
    }     
    fin.close();
}

void vertex_init(int poz) {
    index[poz] = ind;
    lowlink[poz] = ind;
    ind++;
    inStack[poz] = true;
    S.push(poz);
}

void dfs_tarj(int poz) {
     
    vertex_init(poz);    
    vector<int>::iterator it;
    for (it = edges[poz].begin(); it != edges[poz].end(); it++) {
        if (index[*it] == 0) {
            dfs_tarj(*it);
            lowlink[poz] = min(lowlink[poz], lowlink[*it]);                    
        } else if (inStack[*it] == true) {
            lowlink[poz] = min(lowlink[poz], index[*it]);       
        }
    } 
     
    if (lowlink[poz] == index[poz]) {
       vector<int> ctc;
       
       inStack[S.top()] = false;
       ctc.push_back(S.top());
       while (S.top() != poz) {                     
           S.pop();              
           inStack[S.top()] = false;  
           ctc.push_back(S.top());   
       }    
       S.pop();
       
       rez.push_back(ctc);                
    }      
}

void tarjan() {
    for (int i = 1; i <= n; i++) {
        if (index[i] == 0) {
           dfs_tarj(i);           
        }
    }
}

void write_() {
     freopen("ctc.out", "w", stdout);
     vector< vector<int> >::iterator set_it;
     vector<int>::iterator vect_it;
     
     printf("%d \n", rez.size());
     for (set_it = rez.begin(); set_it != rez.end(); set_it++) {
         vector<int> ctc = *set_it;
         for (vect_it = ctc.begin(); vect_it != ctc.end(); vect_it++) {
             printf("%d ", *vect_it);
         } 
         printf("\n");
     }
}

int main() {        
    read_();
    tarjan();
    write_();    
    return 0; 
}