Pagini recente » Cod sursa (job #2809480) | Cod sursa (job #1442533) | Cod sursa (job #2807436) | Cod sursa (job #154206) | Cod sursa (job #2359333)
#include <iostream>
#define nmax 100005
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> G[nmax],GT[nmax],sol2[nmax];
int n,m,nrCTC,viz[nmax],sol1[nmax],k;
void cit()
{f>>n>>m;
for(int i;i<=m;i++)
{int x,y;
f>>x>>y;
G[x].push_back(y);
GT[y].push_back(x)
}
}
void DFSP(int nod)
{viz[nod]=1;
for(unsigned int i=0;i<G[nod].size();i++)
{int vecin=G[nod][i];
if(viz[vecin]==0)
DFSP(vecin);
}
sol1[++k]=nod;
}
void DFSM(int nod)
{viz[nod]=2;
sol2[nrCTC].push_back(Nod);
for(unsigned int i=0;i<GT[nod].size();i++)
{int vecin=GT[nod][i];
DFSM(vecin);
}
}
void solve()
{for(int i=1;i<=n;i++)
if(viz[i]==0) DFSP(i);
for(int i=k;i>=1;i--)
{int nod=sol1[i];
if(viz[nod]==1)
{nrCTC++;
DFSM(nod);
}
}
}
void print()
{g<<nrCTC<<'\n';
for(int i=1;i<=nrCTC;i++)
{for(unsigned int j=0;j<sol2[i].size();j++)
g<<sol2[i][j]<<" ";
g<<'\n';
}
}
int main()
{ cit(); solve(); print(); return 0;
return 0;
}