Pagini recente » Cod sursa (job #1658797) | Cod sursa (job #289803) | Cod sursa (job #1518294) | Cod sursa (job #1829370) | Cod sursa (job #775377)
Cod sursa(job #775377)
#include<fstream>
#include<vector>
#define NMAX 100010
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m, ctc, nr, vz[NMAX], vzt[NMAX], po[NMAX];
vector<int> a[NMAX], at[NMAX], b[NMAX];
void Citeste()
{
int i, x, y;
f>>n>>m;
for (i=1; i<=m; ++i)
{
f>>x>>y;
a[x].push_back(y);
at[y].push_back(x);
}
}
void DFS(int nod)
{
int v, i, lg;
vz[nod]=nr; lg=a[nod].size();
for (i=0; i<lg; ++i)
{
v=a[nod][i];
if (!vz[v]) DFS(v);
}
po[++po[0]]=nod;
}
void DFSt(int nod)
{
vector<int>::iterator it;
if (vz[nod]==nr)
{
vzt[nod]=nr; b[ctc].push_back(nod);
for (it=at[nod].begin(); it!=at[nod].end(); ++it)
if (!vzt[*it]) DFSt(*it);
}
}
void Solve()
{
int nod, i;
for (nod=1; nod<=n; ++nod)
if (!vz[nod])
{
++nr;
DFS(nod);
}
for (i=po[0]; i>0; --i)
{
nod=po[i];
if (!vzt[nod])
{
nr=vz[nod];
++ctc;
DFSt(nod);
}
}
}
void Scrie()
{
int i;
vector<int>::iterator it;
g<<ctc<<"\n";
for (i=1; i<=ctc; ++i)
{
for (it=b[i].begin(); it!=b[i].end(); ++it) g<<*it<<" ";
g<<"\n";
}
}
int main()
{
Citeste();
Solve();
Scrie();
f.close();
g.close();
return 0;
}