Pagini recente » Cod sursa (job #2160984) | Cod sursa (job #1025020) | Cod sursa (job #310424) | Cod sursa (job #37938) | Cod sursa (job #2870397)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX = 100005;
int n, m;
int low_link[NMAX], ids[NMAX], onStack[NMAX];
stack<int>st;
vector<int>G[NMAX];
vector<vector<int>>sol;
void init(int n)
{
for (int i = 1; i <= n; i++)
ids[i] = -1;
while (!st.empty()) st.pop();
}
void read()
{
fin >> n >> m;
while (m--)
{
int a, b;
fin >> a >> b;
G[a].push_back(b);
}
init(n);
}
void dfs(int u)
{
static int value = 0;
st.push(u);
onStack[u] = true;
ids[u] = low_link[u] = ++value;
for (int v : G[u])
{
if (ids[v] == -1)
{
dfs(v);
low_link[u] = min(low_link[u], low_link[v]);
}
else if (onStack[v])
low_link[u] = min(low_link[u], low_link[v]);
}
if (ids[u] == low_link[u])
{
vector<int> v;
while (!st.empty())
{
int nod = st.top();
v.push_back(nod);
onStack[nod] = false;
low_link[nod] = ids[u];
st.pop();
if (nod == u) break;
}
sort(v.begin(), v.end());
sol.push_back(v);
}
}
void tarjan()
{
for (int i = 1; i <= n; i++)
if (ids[i] == -1)
dfs(i);
}
void print(vector<int>& v)
{
for (int e : v)
fout << e << ' ';
fout << '\n';
}
void solve()
{
tarjan();
fout << sol.size() << '\n';
for (vector<int> v : sol)
print(v);
}
int main()
{
read();
solve();
return 0;
}