Pagini recente » Cod sursa (job #774784) | Cod sursa (job #2957783) | Cod sursa (job #1362805) | Cod sursa (job #1524790) | Cod sursa (job #2140718)
#include <fstream>
#include <vector>
#include <cstring>
#define Nmax 100001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int fv[Nmax],st[Nmax],sol,n,m,i,j;
vector <int> g[Nmax],gt[Nmax],ctc[Nmax];
vector <int> :: iterator it;
inline void dfs(int nod)
{
int i;
fv[nod]=1;
for (i=0;i<g[nod].size();i++)
{
if(!fv[g[nod][i]])
dfs(g[nod][i]);
}
st[++st[0]]=nod;
}
inline void dfst(int nod)
{
int i;
fv[nod]=1;
for (i=0;i<gt[nod].size();i++)
{
if(!fv[gt[nod][i]])
dfst(gt[nod][i]);
}
ctc[sol].push_back(nod);
}
int main()
{
fin>>n>>m;
while(fin>>i>>j)
{
g[i].push_back(j);
gt[j].push_back(i);
}
memset(st,0,sizeof(st));
memset(fv,0,sizeof(fv));
for (i=1;i<=n;i++)
{
if(!fv[i])
dfs(i);
}
memset(fv,0,sizeof(fv));
for (i=n;i>0;i--)
{
if(!fv[st[i]])
{
sol++;
dfst(st[i]);
}
}
fout<<sol<<'\n';
for (i=1;i<=sol;i++)
{
for (j=0;j<ctc[i].size();j++)
fout<<ctc[i][j]<<" ";
fout<<'\n';
}
fin.close();
fout.close();
return 0;
}