Pagini recente » Cod sursa (job #1199425) | Cod sursa (job #2988880) | Cod sursa (job #1083230) | Cod sursa (job #277320) | Cod sursa (job #3146863)
#include <fstream>
#include <vector>
using namespace std;
/// Algoritmul lui Tarjan in n
const int NMAX = 1e5;
vector<int> graf[1 + NMAX];
bool vizitat[1 + NMAX];
vector<vector<int>> ctc;
vector<int> stiva;
bool peStiva[1 + NMAX];
int adancime[1 + NMAX];
int adancimeMinimaIntoarcere[1 + NMAX];
void dfs(int nod)
{
stiva.emplace_back(nod);
vizitat[nod] = true;
peStiva[nod] = true;
for (int i = 0; i < graf[nod].size(); ++i)
{
if (!vizitat[graf[nod][i]])
{
adancime[graf[nod][i]] = adancime[nod] + 1;
adancimeMinimaIntoarcere[graf[nod][i]] = adancime[nod] + 1;
dfs(graf[nod][i]);
adancimeMinimaIntoarcere[nod] = min(adancimeMinimaIntoarcere[nod], adancimeMinimaIntoarcere[graf[nod][i]]);
}
else if (peStiva[graf[nod][i]])
{
adancimeMinimaIntoarcere[nod] = min(adancimeMinimaIntoarcere[nod], adancimeMinimaIntoarcere[graf[nod][i]]);
}
}
if (adancime[nod] == adancimeMinimaIntoarcere[nod])
{
ctc.emplace_back();
while (stiva.back() != nod)
{
ctc.back().emplace_back(stiva.back());
peStiva[stiva.back()] = false;
stiva.pop_back();
}
ctc.back().emplace_back(stiva.back());
peStiva[stiva.back()] = false;
stiva.pop_back();
}
/// altfel nimic
}
int main()
{
ifstream in("ctc.in");
ofstream out("ctc.out");
ios_base::sync_with_stdio(false);
in.tie(nullptr);
int n, m;
in >> n >> m;
for (int i = 1; i <= m; ++i)
{
int a, b;
in >> a >> b;
graf[a].emplace_back(b);
}
for (int i = 1; i <= n; ++i)
{
if (!vizitat[i])
{
adancime[i] = 1;
adancimeMinimaIntoarcere[i] = 1;
dfs(i);
}
}
out << ctc.size() << '\n';
for (int i = 0; i < ctc.size(); ++i)
{
for (int j = 0; j < ctc[i].size(); ++j)
out << ctc[i][j] << ' ';
out << '\n';
}
in.close();
out.close();
return 0;
}