Pagini recente » Cod sursa (job #449784) | Cod sursa (job #2672841) | Cod sursa (job #9562) | Cod sursa (job #3228422) | Cod sursa (job #639901)
Cod sursa(job #639901)
#include <fstream>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int max_n=100005;
int n,m;
vector <int> grafn[max_n],graftrans[max_n],con[max_n];
int st[max_n],k=0,nrcon;
bool viz[max_n];
void dfnormal(int nod)
{
viz[nod]=1;
for(int i=0;i<grafn[nod].size();i++)
if(!viz[grafn[nod][i]]) dfnormal(grafn[nod][i]);
st[k]=nod;
k++;
}
void dftrans(int nod)
{
viz[nod]=0;
con[nrcon].push_back(nod);
for(int i=0;i<graftrans[nod].size();i++)
if(viz[graftrans[nod][i]]) dftrans(graftrans[nod][i]);
}
int main()
{
freopen ("ctc.in","r",stdin);
freopen ("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
//f>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
// f>>a>>b;
grafn[a].push_back(b);
graftrans[b].push_back(a);
}
for(int i=1;i<=n;i++)
if(!viz[i]) dfnormal(i);
nrcon=1;
for(int i=n-1;i>=0;i--)
if(viz[st[i]])
{
dftrans(st[i]);
nrcon++;
}
printf("%d",nrcon);
// g<<nrcon;
for(int i=0;i<nrcon;i++)
{
for(int j=0;j<con[i].size();j++)
printf("%d ",con[i][j]);
// g<<con[i][j]<<" ";
printf("\n");
//g<<"\n";
}
return 0;
}