Pagini recente » Cod sursa (job #287954) | Cod sursa (job #2867182) | Cod sursa (job #2548470) | Cod sursa (job #2891597) | Cod sursa (job #1438901)
#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 200001
std::vector<int>graf[NMAX];
std::vector<int>graf_t[NMAX];
std::vector<int>solutie[NMAX];
int n, m;
int index[NMAX], ordine[NMAX];
int k, h;
void DFS(int nod)
{
solutie[h].push_back(nod);
index[nod] = 1;
for (int i = 0; i < graf[nod].size(); i++)
{
if (index[graf[nod][i]] == 0)
{
DFS(graf[nod][i]);
}
}
}
void DFST(int nod)
{
index[nod] = 1;
for (int i = 0; i < graf_t[nod].size(); i++)
{
if (index[graf_t[nod][i]] == 0)
{
DFST(graf_t[nod][i]);
}
}
k++;
ordine[k] = nod;
}
void citire()
{
std::ifstream f("ctc.in");
f >> n >> m;
int x, y;
for (int i = 1; i <= m; i++)
{
f >> x >> y;
graf[x].push_back(y);
graf_t[y].push_back(x);
}
}
int main()
{
citire();
for (int i = 1; i <= n; i++)
{
if (index[i] == 0)
{
DFST(i);
}
}
for (int i = 1; i <= n; i++)
{
index[i] = 0;
}
for (int i = n; i >= 1; i--)
{
if (index[ordine[i]] == 0)
{
h++;
DFS(ordine[i]);
}
}
std::ofstream g("ctc.out");
g << h << "\n";
for (int i = h; i >=1 ; i--)
{
for (int j = 0; j < solutie[i].size(); j++)
{
g << solutie[i][j] << " ";
}
g << "\n";
}
return 0;
}