Pagini recente » Cod sursa (job #235556) | Diferente pentru arhiva-educationala intre reviziile 15 si 13 | Cod sursa (job #3286790) | Diferente pentru arhiva-educationala intre reviziile 13 si 14 | Cod sursa (job #235536)
Cod sursa(job #235536)
#include <stdio.h>
#include <vector>
using namespace std;
#define NMax 100005
#define pb push_back
int N, M, ctc[NMax], times[NMax], t, uz[NMax], cnt;
vector<int> G[NMax], GT[NMax], Sol[NMax];
void df(int nod)
{
int i, sz, x;
uz[nod] = 1;
for (i = 0, sz = G[nod].size(); i < sz; ++i)
if (!uz[x = G[nod][i]])
df(x);
times[++t] = nod;
}
void df2(int nod)
{
int i, sz, x;
ctc[nod] = cnt; Sol[cnt].pb(nod);
for (i = 0, sz = GT[nod].size(); i < sz; ++i)
if (!ctc[x = GT[nod][i]])
df2(x);
}
int main()
{
int i, u, v, sz;
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d %d", &N, &M);
for (; M; --M)
{
scanf("%d %d", &u, &v);
G[u].push_back(v);
GT[v].push_back(u);
}
for (i = 1; i <= N; ++i)
if (!uz[i])
df(i);
for (i = N; i; --i)
if (!ctc[times[i]])
{
++cnt;
df2(times[i]);
}
printf("%d\n", cnt);
for (i = 1; i <= cnt; ++i)
{
for (sz = Sol[i].size(), u = 0; u < sz; ++u)
printf("%d ", Sol[i][u]);
printf("\n");
}
return 0;
}