Pagini recente » Cod sursa (job #1692531) | Cod sursa (job #1911338) | Cod sursa (job #111975) | Cod sursa (job #2148089) | Cod sursa (job #1359839)
#include <fstream>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int NMAX=100005;
vector <int> Gi[NMAX], Ge[NMAX];
int i, n, j, m, Ui[NMAX], Ue[NMAX], n1, n2, U[NMAX], nod, ok, k;
void DFSe(int nod)
{ int k=0;
++Ue[nod];
for (k=0; k<Ge[nod].size(); ++k)
if (!Ue[Ge[nod][k]]) DFSe(Ge[nod][k]);
}
void DFSi(int nod)
{ int k=0;
++Ui[nod];
for (k=0; k<Gi[nod].size(); ++k)
if (!Ui[Gi[nod][k]]) DFSi(Gi[nod][k]);
}
int main()
{ f>>n>>m;
for (; m; --m)
{ f>>i>>j;
Ge[i].push_back(j);
Gi[j].push_back(i);
}
nod=1;
while (!ok)
{ DFSe(nod);
DFSi(nod);
ok=1;
++k;
U[nod]=k;
for (i=1; i<=n; ++i)
if (!U[i])
{ if (Ui[i] && Ue[i]) U[i]=k;
else
{ ok=0;
nod=i;
}
}
}
g<<k<<'\n';
for (i=1; i<=k; ++i)
{ for (j=1; j<=n; ++j)
if (U[j]==i) g<<j<<' ';
g<<'\n';
}
return 0;
}