Pagini recente » Cod sursa (job #1919494) | Cod sursa (job #2375452) | Cod sursa (job #1675100) | Cod sursa (job #2355129) | Cod sursa (job #1659962)
# include <cstdio>
# include <vector>
# include <algorithm>
# include <stack>
using namespace std;
FILE *f = freopen("ctc.in", "r", stdin);
FILE *g = freopen("ctc.out", "w", stdout);
const int N_MAX = 100001;
vector <int> G[N_MAX];
vector <int> sol[N_MAX];
stack <int> S;
int lowlink[N_MAX];
bool in_stiva[N_MAX];
int n, m, index, total;
int idx[N_MAX];
void read()
{
scanf("%d %d", &n, &m);
for (int i=1; i<=m; i++)
{
int x, y;
scanf("%d %d", &x, &y);
G[x].push_back(y);
}
}
void dfs(int nod)
{
index ++;
idx[nod] = index;
lowlink[nod] = index;
S.push(nod);
in_stiva[nod] = true;
for (int i : G[nod])
{
if (!lowlink[i])
{
dfs(i);
lowlink[nod] = min(lowlink[nod], lowlink[i]);
}
else
if (in_stiva[i])
lowlink[nod] = min(lowlink[nod], lowlink[i]);
}
if (lowlink[nod] == idx[nod])
{
int it;
it = S.top();
total ++;
while (it != nod)
{
/// printf("%d ", it);
sol[total].push_back(it);
in_stiva[it] = false;
S.pop();
it = S.top();
}
/// printf("%d ", it);
sol[total].push_back(it);
S.pop();
in_stiva[it] = false;
}
}
void write()
{
printf("%d\n", total);
for (int i=1; i<=total; i++)
{
for (int j : sol[i])
{
printf("%d ", j);
}
printf("\n");
}
}
int main()
{
read();
for (int i=1; i<=n; i++)
{
if (!lowlink[i])
dfs(i);
}
write();
return 0;
}