Cod sursa(job #446011)

Utilizator claudiughGheorghe Claudiu-Dan claudiugh Data 24 aprilie 2010 19:05:36
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 2.45 kb
#include <string.h>
#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

#define WHITE 0
#define GRAY 1
#define BLACK 2

int G[MMAX];
int G_t[MMAX];
int pos[NMAX]; 
int pos_t[NMAX];
int n, m; 
int color[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;
	pos_t[i] = 0; 
    }

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

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

    fin.close(); 
}

void print_graph(int pos[NMAX], int G[MMAX]) {
    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 first_dfs(int u, stack<int> &s) {
    color[u] = GRAY; 
    
    for (int i = pos[u]; i < pos[u + 1]; i++) {
	int v = G[i]; 
	if (color[v] == WHITE) {
	    first_dfs(v, s); 
	}
    }

    s.push(u); 
    color[u] = BLACK; 
}

void dfs_t(int u) {
    color[u] = GRAY; 
    
    for (int i = pos_t[u]; i < pos_t[u + 1]; i++) {
	int v = G_t[i]; 
	if (color[v] == WHITE) {
	    dfs_t(v); 
	}
    }
    
    ctcs[ictc] = u; 
    ictc++; 
    color[u] = BLACK; 
}

int main(void) {
    read_data();
    stack<int> s; 
    memset(color, WHITE, sizeof(color)); 
    for (int u = 0; u < n; u++) {
	if (color[u] == WHITE) {
	    first_dfs(u, s); 
	}
    }
    memset(color, WHITE, sizeof(color)); 
    while (!s.empty()) {
	int u = s.top(); 
	if (color[u] == WHITE) {
	    ctc_no++;
	    dfs_t(u); 
	    // add marker 
	    ctcs[ictc] = END; 
	    ictc++; 
	} 
	s.pop(); 
    }
    
    print_results(); 
}