Cod sursa(job #445987)

Utilizator claudiughGheorghe Claudiu-Dan claudiugh Data 24 aprilie 2010 17:29:16
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 2.35 kb
#include <iostream> 
#include <fstream> 
#include <stack> 
#include <vector> 
#include <list> 

using namespace std; 

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

#define NMAX 100001
#define MMAX 200001

int G[MMAX];
int pos[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 < n; i++) {
	pos[i] = 0; 
    }

    for (int i = 0; i < m; i++) {
	int u, v; 
	fin >> u >> v;
	pos[u - 1]++; 
    }

    for (int i = 1; i < n; i++) {
	pos[i] += pos[i - 1]; 
    }
    pos[n] = pos[n - 1]; 
    
    // take a second walk through input data 
    fin.seekg(0, ios::beg); 

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

    fin.close(); 
}

void print_graph() {
    for (int u = 0; u < n; u++) {
	cout << u << ": ";
	for (int i = pos[u]; i < pos[u + 1]; i++) {
	    int v = G[i];  
	    cout << v << " -> "; 
	}
	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; 

    for (int i = pos[u]; i < pos[u + 1]; i++) {
	int v = G[i]; 
	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(); 
}