Pagini recente » Rezultatele filtrării | Rezultatele filtrării | Borderou de evaluare (job #1833418) | Borderou de evaluare (job #2513245) | Cod sursa (job #470594)
Cod sursa(job #470594)
#include<fstream>
#include<vector>
#include<list>
#include<queue>
#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;
struct Vrf
{
long nod;
long tmp;
};
struct DereferenceCompareVrf : public std::binary_function<Vrf, Vrf, bool>
{
bool operator()(const Vrf lhs, const Vrf rhs) const
{
return lhs.tmp < rhs.tmp;
}
};
priority_queue<Vrf,vector<Vrf>, DereferenceCompareVrf> heap;
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;
Vrf a;
a.nod=x;
a.tmp=timpulet;
heap.push(a);
// 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);
}
for(i=1;i<=n;i++)
if(vizitat[i]==0)
dfs(i);
for(i=1;i<=n;i++)
vizitat[i]=0;
long maxim=1,svI=0;
scc.push_back(lista);
while(!heap.empty())
{
Vrf el;
el.nod=(heap.top()).nod;
heap.pop();
if(vizitat[el.nod]==0)
{
total_scc++;
scc.push_back(lista);
dfs_reverse(el.nod);
}
}
//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;
}