Cod sursa(job #1259290)

Utilizator LegionHagiu Stefan Legion Data 9 noiembrie 2014 21:40:28
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define min(a,b) (a)<(b)?(a):(b)
using namespace std;
struct varfuri
{
	vector<int> varf;
	int numar;
	int radacina;
    int vizitat;
};
vector<vector<int>> solutii;
stack<int> stac;
varfuri graf[100001];
int contor;
void rezolva(int i,int baza)
{
	graf[i].vizitat = baza;
	int local = contor;
	int j;
	stac.push(i);
	graf[i].numar = contor;
	graf[i].radacina = contor;
	contor++;
	for (j = 0; j < graf[i].varf.size(); j++)
	{
		if (graf[graf[i].varf[j]].vizitat == false)
		{
			rezolva(graf[i].varf[j],baza);
			graf[i].radacina = min(graf[i].radacina, graf[graf[i].varf[j]].radacina);
		}
		else if (graf[graf[i].varf[j]].vizitat==baza)
		{
			graf[i].radacina = min(graf[i].radacina, graf[graf[i].varf[j]].numar);
		}
	}
	if (graf[i].numar == graf[i].radacina)
	{
		vector<int> aux;
		while (graf[stac.top()].numar != graf[stac.top()].radacina)
		{
			aux.push_back(stac.top());
			stac.pop();
		}
		aux.push_back(stac.top());
		stac.pop();
		solutii.push_back(aux);
	}
}
int main()
{
	ifstream in("ctc.in");
	ofstream out("ctc.out");
	int i, n, m, x, y;
	in >> n;
	in >> m;
	for (i = 1; i <= m; i++)
	{
		in >> x;
		in >> y;
		graf[x].varf.push_back(y);
		graf[x].vizitat = 0;
	}
	for (i = 1; i <= n; i++)
	{
		if (graf[i].vizitat == 0)
		{
			contor = 1;
			rezolva(i,i);
		}
	}
	out << solutii.size() << "\n";
	int j;
	for (i = 0; i < solutii.size(); i++)
	{
		for (j = 0; j < solutii[i].size(); j++)
		{
			out << solutii[i][j] << " ";
		}
		out << "\n";
	}
}