Pagini recente » Cod sursa (job #2358231) | Cod sursa (job #717952) | Cod sursa (job #1991836) | Cod sursa (job #2516161) | Cod sursa (job #3269212)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <set>
#include <stack>
#define nmax 100001
#define Inf 1000000000
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, k;
vector<int> Graf[nmax];
vector<set<int>> Rez;
int low[nmax], instack[nmax];
stack<int> nodes;
void dfs(int node)
{
low[node] = ++m;
int original = m;
nodes.push(node);
instack[node] = 1;
for (auto i : Graf[node])
{
if (!low[i])
{
dfs(i);
}
if (instack[i])
{
low[node] = min(low[node], low[i]);
}
}
if (low[node] == original)
{
Rez.push_back({});
while (!nodes.empty())
{
Rez.back().insert(nodes.top());
instack[nodes.top()] = 0;
if (nodes.top() == node)
{
nodes.pop();
break;
}
else
nodes.pop();
}
}
}
int main()
{
fin >> n >> m;
for (int i = 1; i <= m; i++)
{
int a, b;
fin >> a >> b;
Graf[a].push_back(b);
}
m = 0;
for (int i = 1; i <= n; i++)
{
if (!low[i])
{
dfs(i);
}
}
fout << Rez.size() << '\n';
for (auto i : Rez)
{
for (auto j : i)
fout << j << " ";
fout << '\n';
}
return 0;
}