Pagini recente » Cod sursa (job #1831309) | Cod sursa (job #408371) | Cod sursa (job #1106419) | Cod sursa (job #2407630) | Cod sursa (job #2926077)
#include <iostream>
#include <fstream>
// #include "Graph.cc"
#include <vector>
#include <deque>
#include <algorithm>
const int nrMagic = 100001;
int low[nrMagic], id[nrMagic], revId[nrMagic];
std::vector<std::vector<int>> v(nrMagic);
std::vector<int> viz(nrMagic, 0);
std::deque<int> stack;
int ret = 0, inc = 1, tine = 0;
std::vector<std::vector<int>> parc(nrMagic);
void dfs(const int &nod)
{
// Facem o parcurgere dfs normala doar ca fiecarui nod ii asociem un id si un lowlink value
viz[nod] = 1;
stack.push_back(inc); //punem intr-o stiva id-urile nodurilor
low[nod] = inc; // valoarea minima a nodurilor in care putem merge
revId[inc] = nod; // id -> actual nod
id[nod] = inc++; //actual nod -> id
for (auto &&i : v[nod])
{
if (viz[i] == 0)
{
dfs(i);
}
// cand terminam parcurgerea facem update la low daca nodul nu face parte deja dintr-o componenta conexa
if (std::find(stack.begin(), stack.end(), id[i]) != stack.end())
{
low[nod] = std::min(low[nod], low[i]);
}
}
if (id[nod] == low[nod]) // daca am gasit o componenta conexa
{
while (stack.back() != id[nod])
{
parc[tine].push_back(revId[stack.back()]);
stack.pop_back();
}
parc[tine].push_back(revId[stack.back()]);
stack.pop_back();
ret++;
tine++;
}
}
// Complexitate: O(m + n)
int main()
{
std::ifstream cin("ctc.in");
std::ofstream cout("ctc.out");
unsigned int n, m;
cin >> n >> m;
for (size_t i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
v[a].push_back(b);
}
for (size_t i = 1; i <= n; i++)
{
if (viz[i] == 0)
{
dfs(i);
}
}
cout << ret << '\n';
for (size_t i = 0; i < tine; i++)
{
for (auto &&j : parc[i])
{
cout << j << " ";
}
cout << "\n";
}
}