Cod sursa(job #445990)

Utilizator claudiughGheorghe Claudiu-Dan claudiugh Data 24 aprilie 2010 17:51:02
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 2.16 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
#define END -1

int G[MMAX];
int pos[NMAX]; 
int n, m; 
int T = 0; 
int td[NMAX]; 
int low[NMAX]; 
bool onstack[NMAX]; 
int ctc_no = 0; 
int ictc = 0; 
int ctcs[2 * NMAX]; 

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_results() {
    ofstream fout; 
    fout.open(FILEOUT); 
    fout << ctc_no << endl; 
    for (int i = 0, ic = 0; i < ctc_no; ic++) {
	if (ctcs[ic] != END) {
	    fout << ctcs[ic] + 1 << " "; 
	} else {
	    i++; 
	    fout << endl; 
	}
    }
    fout.close(); 
}

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 
	ctc_no++; 
	while (!s.empty()) {
	    int v = s.top(); 
	    ctcs[ictc] = v;
	    ictc++; 
	    onstack[v] = false; 
	    s.pop();
	    if (v == u) 
		break; 
	}
	ctcs[ictc] = END; 
	ictc++; 
    }
}

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(); 
}