Pagini recente » Cod sursa (job #1712893) | Cod sursa (job #1631114) | Cod sursa (job #2396277) | Cod sursa (job #70731) | Cod sursa (job #2086387)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int MaxN = 100005;
int n, m, seen[MaxN], onst[MaxN], low[MaxN], nrc, ind;
vector<int> gr[MaxN], comp[MaxN];
stack<int> st;
void dfs(int node)
{
seen[node] = ++ind;
st.push(node);
onst[node] = 1;
low[node] = seen[node];
for (auto son: gr[node])
if (!seen[son])
{
dfs(son);
low[node] = min(low[node], low[son]);
}
else if (onst[son]) low[node] = min(low[node], seen[son]);
if (low[node] == seen[node])
{
++nrc;
while (st.top() != node)
{
comp[nrc].push_back(st.top());
onst[st.top()] = 0;
st.pop();
}
comp[nrc].push_back(st.top());
onst[st.top()] = 0;
st.pop();
}
}
int main()
{
f >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y;
f >> x >> y;
gr[x].push_back(y);
}
for (int i = 1; i <= n; i++) if (!seen[i]) dfs(i);
g << nrc << '\n';
for (int i = 1; i <= nrc; i++)
{
for (auto x: comp[i]) g << x << ' ';
g << '\n';
}
return 0;
}