Pagini recente » Cod sursa (job #1674958) | Cod sursa (job #275332) | Cod sursa (job #281595) | Cod sursa (job #956471) | Cod sursa (job #2836205)
#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, x, y;
typedef struct graf
{
int x;
graf* a;
}*L;
L a[100005];
L at[100005];
int f[100005];
int f2[100005];
int stiva[100005];
int rez[100005];
int vf = 0;
int ans = 0;
void add(L& DEST, int val)
{
L p = new graf;
p->x = val;
p->a = DEST;
DEST = p;
}
void citire()
{
fin >> n >> m;
for (int i = 1; i <= m; i++)
{
fin >> x >> y;
add(a[x], y);
add(at[y], x);
}
}
void DFS1(int nod)
{
f[nod] = 1;
for (L p = a[nod]; p != NULL; p = p->a)
{
if (!f[p->x])
DFS1(p->x);
}
stiva[++vf] = nod;
}
void DFS_STRONG(int nod,int index)
{
f2[nod] = 1;
rez[nod] = index;
for (L p = at[nod]; p != NULL; p = p->a)
{
if (!f2[p->x])
DFS_STRONG(p->x,index);
}
}
void rezolvare()
{
for (int i = 1; i <= n; i++) {
if (!f[i]) DFS1(i);
}
while (vf)
{
int k = stiva[vf--];
if (!f2[k])
{
ans++;
DFS_STRONG(k,ans);
}
}
fout << ans << '\n';
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (rez[j] == i) fout << j << ' ';
}
fout << '\n';
}
}
int main()
{
citire();
rezolvare();
}