Cod sursa(job #444410)

Utilizator claudiughGheorghe Claudiu-Dan claudiugh Data 20 aprilie 2010 13:47:04
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 kb
#include <iostream> 
#include <fstream> 
#include <stack> 
#include <vector> 
#include <list> 

using namespace std; 

#define FILEIN "ctc.in" 
#define FILEOUT "ctc.out" 

#define NMAX 1000

list<int> G[NMAX]; 
int n, m; 
int T = 0; 
int td[NMAX]; 
int low[NMAX]; 
bool onstack[NMAX]; 
list<list<int>* >ctcs; 

void read_data() {
    ifstream fin; 
    fin.open(FILEIN); 

    fin >> n >> m; 
    for (int i = 0; i < m; i++) {
	int u, v; 
	fin >> u >> v; 
	G[u - 1].push_back(v - 1); 
    }
    fin.close(); 
}

void print_graph() {
    for (int u = 0; u < n; u++) {
	cout << u << ": "; 
	list<int>::const_iterator it; 
	for (it = G[u].begin(); it != G[u].end(); it++) {
	    cout << *it << " -> "; 
	}
	cout << endl; 
    }
}

void print_ctc(ofstream &f, list<int> *ctc) {
    list<int>::const_iterator it; 
    for (it = ctc->begin(); it != ctc->end(); it++) {
	int u = *it + 1; 
	f << u << " "; 
    }
    f << endl; 
}

void print_results() {
    ofstream fout; 
    fout.open(FILEOUT); 
    fout << ctcs.size() << endl; 
    list<list<int>* >::const_iterator it; 
    for (it = ctcs.begin(); it != ctcs.end(); it++) {
	print_ctc(fout, *it); 
    }

    fout.close(); 
}

void add_ctc(list<int> *ctc) {
    ctcs.push_back(ctc); 
}

void dfs_tarjan(int u, stack<int> &s) {
    td[u] = T;
    low[u] = T; 
    T++; 
    s.push(u); 
    onstack[u] = true; 

    list<int>::const_iterator it; 
    for (it = G[u].begin(); it != G[u].end(); it++) {
	int v = *it; 
	if (td[v] < 0) {
	    dfs_tarjan(v, s); 
	}

	if (onstack[v]) {
	    if (low[v] < low[u])
		low[u] = low[v];
	}
    }

    if (low[u] == td[u]) {
	// is root 
	list<int> *ctc = new list<int>(); 
	while (!s.empty()) {
	    int v = s.top(); 
	    ctc->push_back(v);
	    onstack[v] = false; 
	    s.pop();
	    if (v == u) 
		break; 
	}
	add_ctc(ctc); 
    }
}

int main(void) {
    read_data(); 
    stack<int> s; 
    // init 
    for (int i = 0; i < n; i++) {
	low[i] = -1; 
	td[i] = -1; 
	onstack[i] = false; 
    }

    for (int i = 0; i < n; i++) {
	if (td[i] < 0)
	    dfs_tarjan(i, s); 
    }
    print_results(); 
}