Pagini recente » Cod sursa (job #1829643) | Cod sursa (job #315612) | Cod sursa (job #1593466) | Cod sursa (job #2727086) | Cod sursa (job #2376444)
#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 > G[maxN];
static int t = 0;
int disc[maxN], low[maxN], st[maxN], comp[maxN];
int top;
bool inSt[maxN];
int ans;
vector < int > C[maxN];
void dfs(int u)
{
disc[u] = low[u] = ++ t;
inSt[u] = true;
st[++ top] = u;
for (int v : G[u])
if (!disc[v])
{
dfs(v);
low[u] = min(low[u], low[v]);
}
else if (inSt[v])
low[u] = min(low[u], disc[v]);
if (disc[u] == low[u])
{
comp[u] = ans;
while (st[top] != u)
{
comp[st[top]] = ans;
inSt[st[top]] = false;
C[ans].push_back(st[top]);
-- top;
}
C[ans].push_back(u);
inSt[u] = false;
-- top;
++ ans;
}
}
int main()
{
scanf("%d%d", &n, &m);
while (m --)
{
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
}
for (int i = 1; i <= n; ++ i)
if (!disc[i])
dfs(i);
printf("%d\n", ans);
for (int i = 1; i <= n; ++ i)
if (!inSt[comp[i]])
{
int j = comp[i];
inSt[j] = true;
sort(C[j].begin(), C[j].end());
for (int u : C[j])
printf("%d ", u);
printf("\n");
}
return 0;
}