Cod sursa(job #1182207)

Utilizator MarianMMorosac George Marian MarianM Data 5 mai 2014 01:56:11
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <list>
#include <algorithm>
using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

#define DMAX 11

struct Graph{
	char inf[DMAX];			// content
	char color[DMAX];		// w->g->b
	int parent[DMAX], d[DMAX], f[DMAX];		// d = discovered, f = finished
	vector<int> Adj[DMAX], AdjT[DMAX];	// Adj list
	vector<pair<int, int>> Edge, EdgeT;
} G;

int N, M, time, ok, nrCTC;
vector<int> CTC[DMAX];

list<int> L;
list<int>::iterator l;

void DFS_VISIT(int root){
	int i, lg, next;

	time++;
	G.color[root] = 'g';
	G.d[root] = time;
	if (ok == 2) CTC[nrCTC].push_back(root);

	if(ok==1) lg = G.Adj[root].size();
	else lg = G.AdjT[root].size();
	
	for (i = 0; i < lg; i++){
		if (ok == 1) next = G.Adj[root][i];
		else next = G.AdjT[root][i];

		if (G.color[next] == 'w')
			DFS_VISIT(next);
	}

	time++;
	G.color[root] = 'b';
	G.f[root] = time;
	if (ok == 1) L.push_front(root);
}

void DFS(){
	int i;

	for (i = 1; i <= N; i++){
		G.color[i] = 'w';
		G.parent[i] = 0;
	}

	if (ok == 1){
		for (i = 1; i <= N; i++){
			if (G.color[i] == 'w'){
				DFS_VISIT(i);
			}
		}
	}
	else{
		for (l = L.begin(); l != L.end(); l++)	
		if (G.color[*l] == 'w'){
			nrCTC++;
			DFS_VISIT(*l);
		}
	}
}

int main(){
	int i, j, ui, vi, lg;

	fin >> N >> M;
	for (i = 0; i < M; i++) {
		fin >> ui >> vi;
		G.Adj[ui].push_back(vi);
		G.AdjT[vi].push_back(ui);
		G.Edge.push_back(make_pair(ui, vi));
		G.EdgeT.push_back(make_pair(vi, ui));
	}

	ok = 1;  DFS();
	ok = 2;  DFS();

	fout << nrCTC << '\n';
	for (i = 1; i <= nrCTC; i++){
		lg = CTC[i].size();
		for (j = 0; j < lg; j++) fout << CTC[i][j] << ' ';
		fout << '\n';
	}

	return 0;
}