Cod sursa(job #760749)

Utilizator cvicentiuCiorbaru Vicentiu Marian cvicentiu Data 22 iunie 2012 20:06:25
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<stdio.h>
#include<vector>
#include<list>

using namespace std;

void dfs(int src, vector<bool> &viz, vector<list<int> > &G, list<int> &q) {
	viz[src] = true;
	list<int>::iterator it;
	for (it = G[src].begin(); it != G[src].end(); it++) {
		if (viz[*it] == false) {
			dfs(*it, viz, G, q);
			q.push_front(*it);
		}
	}
}
int main() {
	FILE *f = fopen("ctc.in", "r");
	FILE *g = fopen("ctc.out", "w");
	int n, m;
	fscanf(f, "%d%d", &n, &m);
	vector<list<int> > G(n);
	vector<list<int> > GT(n);
	vector<bool> viz1(n, false);
	vector<bool> viz2(n, false);
	for (int i = 0; i < m; i++) {
		int x1, x2;
		fscanf(f, "%d%d", &x1, &x2);
		G[x1-1].push_back(x2-1);
		GT[x2-1].push_back(x1-1);
	}
	list<int> queue;
	for (int i = 0; i < n; i++) {
		if (viz1[i] == false) {
			dfs(i, viz1, G, queue);
			queue.push_front(i);
		}
	}
	list<int>::iterator it;
	vector<list<int> > comp;
	for (it = queue.begin(); it != queue.end(); it++) {
		if (viz2[*it] == false) {
			list<int> ctc;
			dfs(*it, viz2, GT, ctc);
			ctc.push_back(*it);
			comp.push_back(ctc);
		}
	}
	fprintf(g, "%d\n", comp.size());
	for (int i = 0; i < comp.size(); i++) {
		for(it = comp[i].begin(); it != comp[i].end(); it++) {
			fprintf(g, "%d ", (*it) + 1);
		}
		fprintf(g, "\n");
	}
	fclose(f);
	fclose(g);
}