Pagini recente » Cod sursa (job #1671151) | Cod sursa (job #1793474) | Cod sursa (job #936149) | Cod sursa (job #1827972) | Cod sursa (job #1165305)
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N, M;
vector<int> V[100002];
int where[100002], whmin[100002];
int comps;
vector<int> comp[100002];
int ST[100002];
bool inST[100002];
void Tarjan(int x)
{
where[x] = ++where[0];
whmin[x] = where[x];
ST[++ST[0]] = x;
inST[x] = true;
for (auto it = V[x].begin(); it != V[x].end(); ++it)
{
if (!where[*it])
Tarjan(*it);
if (inST[*it])
whmin[x] = min(whmin[x], whmin[*it]);
}
if (where[x] == whmin[x])
{
++comps;
while (true)
{
comp[comps].push_back(ST[ST[0]]);
--ST[0];
inST[ST[ST[0] + 1]] = false;
if (ST[ST[0] + 1] == x) break;
}
}
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d %d", &N, &M);
for (int i = 1, nod1, nod2; i <= M; ++i)
{
scanf("%d %d", &nod1, &nod2);
V[nod1].push_back(nod2);
}
for (int i = 1; i <= N; ++i)
if (!where[i])
Tarjan(i);
printf("%d\n", comps);
for (int i = 1; i <= comps; ++i)
{
for (auto it = comp[i].begin(); it != comp[i].end(); ++it)
printf("%d ", *it);
printf("\n");
}
}