Pagini recente » Cod sursa (job #86111) | Cod sursa (job #220593) | Cod sursa (job #2077864) | Cod sursa (job #2888002) | Cod sursa (job #3196277)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
const int NMAX = 100001;
const int INF = 1e9;
std::ifstream fin("ctc.in");
std::ofstream fout("ctc.out");
int N, M, Start;
std::vector<int>G[NMAX];
std::vector<int>GT[NMAX];
std::stack<int>Sortare_Topologica;
int Viz[NMAX], Viz2[NMAX];
int Dist[NMAX];
int Tata[NMAX];
bool Possible = true;
int eStiva[NMAX];
std::vector<int>Componente_Tare[NMAX];
void Citire()
{
fin >> N >> M;
for (int i = 1; i <= M; ++i)
{
int x, y;
fin >> x >> y;
G[x].push_back(y);
GT[y].push_back(x);
}
}
void Dfs(int nod)
{
Viz[nod] = 1;
eStiva[nod] = true;
for (auto& x : G[nod])
{
if (!Viz[x])
Dfs(x);
}
eStiva[nod] = false;
Sortare_Topologica.push(nod);
}
void Dfs2(int nod, int tura)
{
Viz2[nod] = 1;
Componente_Tare[tura].push_back(nod);
for (auto& x : GT[nod])
{
if (!Viz2[x])
Dfs2(x, tura);
}
}
void Sortez()
{
for (int i = 1; i <= N; ++i)
{
if (!Viz[i])
Dfs(i);
}
int comp_tare = 1;
while (!Sortare_Topologica.empty())
{
int nod = Sortare_Topologica.top();
Sortare_Topologica.pop();
if (!Viz2[nod])
{
Dfs2(nod, comp_tare);
comp_tare++;
}
}
fout << comp_tare - 1 << '\n';
for (int i = 1; i < comp_tare; ++i)
{
for (auto& x : Componente_Tare[i])
fout << x << " ";
fout << '\n';
}
}
void Afisare()
{
if (!Possible)
std::cout << "IMPOSSIBLE";
else
{
int ordine = 1;
while (!Sortare_Topologica.empty())
{
fout << Sortare_Topologica.top() << " ";
Sortare_Topologica.pop();
}
}
}
int main()
{
Citire();
Sortez();
//Afisare();
}