Pagini recente » Cod sursa (job #131684) | Cod sursa (job #348063) | Cod sursa (job #2280280) | Cod sursa (job #2124131) | Cod sursa (job #1232495)
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#define NMAX 100002
using namespace std;
ifstream in ("ctc.in");
ofstream out ("ctc.out");
int timp[NMAX], n, nr, i, p, j, num, u ,v, sol[NMAX], m, rez[NMAX];
bool viz[NMAX];
vector<int> g[NMAX], gt[NMAX];
void DFSg (int u)
{
for (int i=0; i<g[u].size(); i++)
{
if(!viz[g[u][i]])
{
viz[g[u][i]]=1;
DFSg(g[u][i]);
}
}
timp[++num] = u;
}
void DFSgt (int u)
{ m++;
sol[m]=u;
for (int i=0; i<gt[u].size(); i++)
{
if(!viz[gt[u][i]])
{
viz[gt[u][i]]=1;
//rez[p].push_back(gt[u][i]);
DFSgt(gt[u][i]);
}
}
}
int main()
{
in>>n>>nr;
for (i=1; i<=nr; i++)
{
in>>u>>v;
g[u].push_back(v);
gt[v].push_back(u);
}
for (i=1; i<=n; i++)
if (!viz[i])
{
viz[i]=1;
DFSg(i);
}
/* for (i=1; i<=n; i++)
{
sort(gt[i].begin(),gt[i].end(),cmp);
}*/
memset(viz,0,sizeof(viz));
for (i=n; i>=1; i--)
{
if (!viz[timp[i]])
{ p++;
rez[p]=m+1;
viz[timp[i]]=1;
//p++;
//rez[p].push_back(i);
DFSgt(timp[i]);
}
}
out<<p<<'\n';
for (i=1; i<=p; i++)
{
for (j=rez[i]; j<rez[i+1]; j++)
out<<sol[j]<<' ';
out<<'\n';
}
return 0;
}