Pagini recente » Cod sursa (job #1060338) | Cod sursa (job #2399130) | Cod sursa (job #2915816) | Cod sursa (job #933454) | Cod sursa (job #1232429)
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#define NMAX 100 001
using namespace std;
ifstream in ("ctc.in");
ofstream out ("ctc.out");
int timp[NMAX], t, n, nr, i, p, j, u ,v;
bool cmp(int x,int y)
{
return timp[x]>timp[y];
}
bool viz[NMAX];
vector<int> g[NMAX], gt[NMAX] ,rez[NMAX];
int DFSg (int u)
{
int i=0;
viz[u]=1;
t++;
for (i=0; i<g[u].size(); i++)
{
if(!viz[g[u][i]]) DFSg(g[u][i]);
}
timp[u] = ++t;
}
int DFSgt (int u)
{
int i=0;
viz[u]=1;
//rez.push_back(u);
for (i=0; i<gt[u].size(); i++)
{
if(!viz[gt[u][i]])
{
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])
DFSg(i);
for (i=1; i<=n; i++)
{
sort(gt[i].begin(),gt[i].end(),cmp);
}
memset(viz,0,sizeof(viz));
// out<<p-1<<'\n';
p=0;
for (i=1; i<=n; i++)
{
if (!viz[i])
{ p++;
rez[p].push_back(i);
DFSgt(i);
//p++;
//for (int j=0; j<rez.size(); j++)
//out<<rez[j]<<' ';
//out<<'\n';
}
//rez.clear();
}
out<<p<<'\n';
for (i=1;i<=p;i++)
{for (j=0; j<rez[i].size(); j++)
out<<rez[i][j]<<' ';
out<<'\n';}
return 0;
}