Cod sursa(job #2359333)

Utilizator valentin12Valentin Ion Semen valentin12 Data 28 februarie 2019 19:41:05
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#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;
}