Pagini recente » Cod sursa (job #1036086) | Cod sursa (job #2116998) | Cod sursa (job #3166698) | Cod sursa (job #731939) | Cod sursa (job #2377138)
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
#define N 100001
using namespace std;
typedef unsigned int uint;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
uint n, m, timp, lowlink[N], v[N];
bool inStack[N];
vector<vector<uint>> adj, sol;
stack<uint> S;
void SSC(uint node)
{
S.push(node);
inStack[node] = true;
lowlink[node] = v[node] = ++timp;
for (auto &i : adj[node])
{
if (!v[i])
{
SSC(i);
lowlink[node] = min(lowlink[node], lowlink[i]);
}
else if (inStack[i])
{
lowlink[node] = min(lowlink[node], lowlink[i]);
}
}
if (lowlink[node] == v[node])
{
sol.emplace_back(vector<uint>());
while (S.top() != node)
{
sol.back().emplace_back(S.top());
inStack[S.top()] = false;
S.pop();
}
sol.back().emplace_back(S.top());
inStack[S.top()] = false;
S.pop();
}
}
void Tarjan()
{
for (uint i = 1; i <= n; ++i)
{
if (!v[i])
SSC(i);
}
fout << sol.size() << '\n';
for (auto &i : sol)
{
for (auto &j : i)
fout << j << ' ';
fout << '\n';
}
}
int main()
{
fin >> n >> m;
adj.assign(n + 1, vector<uint>());
for (uint x,y,i = 0; i < m; ++i)
{
fin >> x >> y;
adj[x].emplace_back(y);
}
Tarjan();
}