Pagini recente » Cod sursa (job #180374) | Cod sursa (job #1207710) | Cod sursa (job #637475) | Cod sursa (job #1680217) | Cod sursa (job #1259152)
#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;
bool vizitat;
};
vector<vector<int>> solutii;
stack<int> stac;
varfuri graf[100001];
int contor;
void rezolva(int i)
{
graf[i].vizitat = true;
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]);
graf[i].radacina = min(graf[i].radacina, graf[graf[i].varf[j]].radacina);
}
else
{
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);
}
}
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";
}
}