Pagini recente » Cod sursa (job #317706) | Cod sursa (job #550950) | Cod sursa (job #692278) | Cod sursa (job #417125) | Cod sursa (job #2806127)
#include <cstdio>
#include <deque>
#include <vector>
using namespace std;
FILE* f, * g;
int n, m;
int starttr[100002], start[100002], t[2][200002], ttr[2][200002], sol;
bool viz[100002];
int q[100002];
vector <int> a[100002];
void dfstr(int nod)
{
int poz, vecin;
viz[nod] = 1;
poz = starttr[nod];
while (poz)
{
vecin = ttr[0][poz];
if (!viz[vecin])
dfstr(vecin);
poz = ttr[1][poz];
}
a[sol].push_back(nod);
}
void dfs(int nod)
{
int poz, vecin;
poz = start[nod];
viz[nod] = 1;
while (poz)
{
vecin = t[0][poz];
if (!viz[vecin])
dfs(vecin);
poz = t[1][poz];
}
q[++q[0]] = nod;
}
int main()
{
f = fopen("ctc.in", "r");
g = fopen("ctc.out", "w");
fscanf(f, "%d %d", &n, &m);
int k1 = 0, k2 = 0, x, y;
for (int i = 1;i <= m;++i)
{
fscanf(f, "%d %d", &x, &y);
t[0][++k1] = y;
t[1][k1] = start[x];
start[x] = k1;
ttr[0][++k2] = x;
ttr[1][k2] = starttr[y];
starttr[y] = k2;
}
for (int i = 1;i <= n;++i)
if (!viz[i])
dfs(i);
for (int i = 1;i <= n;++i)
viz[i] = 0;
for (int i = n;i >= 1;--i)
if (!viz[q[i]])
++sol, dfstr(q[i]);
fprintf(g, "%d\n", sol);
for (int i = 1;i <= sol;++i)
{
for (int j = 0;j < a[i].size();++j)
fprintf(g, "%d ", a[i][j]);
fprintf(g, "\n");
}
fclose(f);
fclose(g);
return 0;
}