Pagini recente » Cod sursa (job #1416326) | Cod sursa (job #430449) | Cod sursa (job #69125) | Cod sursa (job #2291600) | Cod sursa (job #2792027)
#include <fstream>
#include <vector>
#define NMAX 100009
std::ifstream f("ctc.in");
std::ofstream g("ctc.out");
int N, M;
std::vector<int> Adiacenta[NMAX];
std::vector<int> t_Adiacenta[NMAX]; // Transpus
std::vector<std::vector<int>> compTC;
int stivaTopo[NMAX], stVf;
bool vizitat[NMAX];
void Dfs(int nod)
{
vizitat[nod] = true;
for (auto& vecin : Adiacenta[nod])
if (!vizitat[vecin])
Dfs(vecin);
stivaTopo[++stVf] = nod;
}
void t_Dfs(int nod)
{
vizitat[nod] = true;
for (auto& vecin : t_Adiacenta[nod])
if (!vizitat[vecin])
t_Dfs(vecin);
compTC.back().push_back(nod);
}
int main()
{
f >> N >> M;
for (int x, y, i = 0; i < M; ++i)
{
f >> x >> y;
Adiacenta[x].push_back(y);
t_Adiacenta[y].push_back(x);
}
for (int nod = 1; nod <= N; ++nod)
if (!vizitat[nod])
Dfs(nod);
for (int nod = 1; nod <= N; ++nod)
vizitat[nod] = false;
while (stVf)
{
if (!vizitat[stivaTopo[stVf]])
{
compTC.push_back({});
t_Dfs(stivaTopo[stVf]);
}
--stVf;
}
g << compTC.size() << '\n';
for (auto& comp : compTC)
{
for (auto& nod : comp)
g << nod << ' ';
g << '\n';
}
return 0;
}