Pagini recente » Cod sursa (job #2442216) | Cod sursa (job #2164609) | Cod sursa (job #1755052) | Cod sursa (job #2936504) | Cod sursa (job #1971503)
#include <fstream>
#include <vector>
#define Ndim 100001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int ST[Ndim],Low[Ndim],Lev[Ndim],ctc,niv;
bool VIZ[Ndim];
vector <int> G[Ndim],SOL[Ndim];
void strongConnect(int nod)
{
VIZ[nod] = 1;
++niv;
Low[nod] = Lev[nod] = niv;
ST[++ST[0]] = nod;
for(vector <int> :: iterator it = G[nod].begin();it!=G[nod].end();++it)
{
if(!Lev[*it])
{
strongConnect(*it);
Low[nod] = min(Low[nod],Low[*it]);
}
else if(VIZ[*it]==1)
Low[nod] = min(Lev[nod],Low[*it]);
}
if(Lev[nod] == Low[nod])
{
ctc++;
do
{
SOL[ctc].push_back(ST[ST[0]]);
VIZ[ST[ST[0]]] = 0;
ST[0]--;
}while(ST[ST[0]+1]!=nod);
}
}
int main()
{
int n,m,i,a,b;
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>a>>b;
G[a].push_back(b);
}
for(i=1;i<=n;i++)
{
if(!Lev[i])
strongConnect(i);
}
fout<<ctc<<'\n';
for(i=1;i<=ctc;i++,fout<<'\n')
for(vector<int> :: iterator it = SOL[i].begin();it!=SOL[i].end();++it)
fout<<*it<<' ';
return 0;
}