Pagini recente » Cod sursa (job #208876) | Profil fetitele_powerpuff | Cod sursa (job #726049) | Cod sursa (job #200145) | Cod sursa (job #470536)
Cod sursa(job #470536)
#include<fstream>
#include<vector>
#include<list>
#define NMAX 100005
using namespace std;
long n,m,d[NMAX],f[NMAX],vizitat[NMAX],total_scc;
long timpulet;
vector<list<long> > G,GT;
vector<list<long> > scc;
void dfs(int x)
{
vizitat[x]=1;
list<long>::iterator itr;
for(itr=G[x].begin(); itr!=G[x].end(); itr++)
if(vizitat[*itr]==0)
{
timpulet+=1;
d[*itr]=timpulet;
vizitat[*itr]=1;
dfs(*itr);
}
timpulet+=1;
f[x]=timpulet;
}
void dfs_reverse(int x)
{
vizitat[x]=1;
scc[total_scc].push_back(x);
f[x]=0;
list<long>::iterator itr;
for(itr=GT[x].begin(); itr!=GT[x].end(); itr++)
if(vizitat[*itr]==0)
{
// d[*itr]=++timpulet;
vizitat[*itr]=1;
dfs_reverse(*itr);
}
//f[x]=++timpulet;
}
int main()
{
fstream fin,fout;
long i,x,y;
list<long> lista;
fin.open("ctc.in",ios::in);
fout.open("ctc.out",ios::out);
fin>>n>>m;
for(i=0;i<=n;i++)
{
G.push_back(lista);
GT.push_back(lista);
d[i]=f[i]=0;
}
for(i=1;i<=m;i++)
{
fin>>x>>y;
G[x].push_back(y);
GT[y].push_back(x);
}
dfs(1);
for(i=1;i<=n;i++)
vizitat[i]=0;
long maxim=1,svI=0;
scc.push_back(lista);
while(maxim!=0)
{
maxim=0;
for(i=1;i<=n;i++)
if(f[i]>maxim)
{
svI=i;
maxim=f[i];
}
if(maxim!=0)
{
total_scc++;
scc.push_back(lista);
dfs_reverse(svI);
}
}
vector<list<long> >::iterator vItr;
list<long>::iterator lItr;
fout<<total_scc<<'\n';
vItr=scc.begin();
vItr++;
for(vItr=vItr; vItr!=scc.end(); vItr++)
{
for(lItr=(*vItr).begin(); lItr!=(*vItr).end(); ++lItr)
fout<<*lItr<<" ";
fout<<'\n';
}
fin.close();
fout.close();
return 0;
}