Pagini recente » Cod sursa (job #90369) | Cod sursa (job #802581) | Cod sursa (job #1453453) | Cod sursa (job #2850557) | Cod sursa (job #2416282)
#include <bits/stdc++.h>
#define maxN 100002
using namespace std;
FILE *fin = freopen("ctc.in", "r", stdin);
FILE *fout = freopen("ctc.out", "w", stdout);
int n, m;
vector < int > V[maxN];
int T, disc[maxN], low[maxN], nrC;
bool inSt[maxN];
int top, st[maxN];
vector < int > C[maxN];
void Ctc(int u)
{
++ nrC;
while (top > 0)
{
int crt = st[top];
-- top;
C[nrC].push_back(crt);
inSt[crt] = false;
if (crt == u) break;
}
}
void dfs(int u, int par)
{
disc[u] = low[u] = ++ T;
st[++ top] = u;
inSt[u] = true;
for (int v : V[u])
if (!disc[v])
{
dfs(v, u);
low[u] = min(low[u], low[v]);
}
else if (inSt[v])
{
low[u] = min(low[u], disc[v]);
}
if (low[u] == disc[u])
Ctc(u);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++ i)
{
int u, v;
scanf("%d%d", &u, &v);
-- u;
-- v;
V[u].push_back(v);
}
for (int i = 0; i < n; ++ i)
if (!disc[i])
dfs(i, -1);
printf("%d\n", nrC);
for (int i = 1; i <= nrC; ++ i, printf("\n"))
for (auto it : C[i])
printf("%d ", it + 1);
return 0;
}