Pagini recente » Cod sursa (job #2324228) | Cod sursa (job #2610035) | Cod sursa (job #524283) | Cod sursa (job #1169114) | Cod sursa (job #979308)
Cod sursa(job #979308)
#include <fstream>
#include <bitset>
#include <list>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
struct nod
{
list<int> vecini;
list<int> vecini_rev;
}v[900005];
bitset<900005> viz;
bitset<900005> viz_rev;
int ordine[900005];
int termin;
stack<int> stiva;
int nod;
void dfs_rev()
{
list<int>::iterator it;
stiva.push(nod);
int curent;
while(!stiva.empty())
{
curent=stiva.top();
stiva.pop();
for(it=v[curent].vecini_rev.begin();it!=v[curent].vecini_rev.end();it++)
if(!viz_rev[*it])
{
viz_rev[*it]=1;
stiva.push(*it);
}
ordine[termin++]=curent;
}
}
vector<list<int> > componente;
int cate;
void dfs()
{
list<int>::iterator it;
stiva.push(nod);
int curent;
while(!stiva.empty())
{
curent=stiva.top();
stiva.pop();
componente[cate].push_back(curent);
for(it=v[curent].vecini.begin();it!=v[curent].vecini.end();it++)
if(!viz[*it])
{
viz[*it]=1;
stiva.push(*it);
}
}
}
bool comp(int a,int b)
{
if(a>b)
return 1;
return 0;
}
int main()
{
ifstream fin("ctc.in");
ofstream fout("ctc.out");
cate=0;
int n,m=0,i,a,b;
// n=875714;
fin>>n>>m;
//while(fin>>a>>b)
for(i=0;i<m;i++)
{
fin>>a>>b;
v[a].vecini.push_back(b);
v[b].vecini_rev.push_back(a);
//m++;
}
termin=1;
for(i=1;i<=n;i++)
if(!viz_rev[i])
{
nod=i;
viz_rev[i]=1;
dfs_rev();
}
//cout<<"pas 1 gata"<<endl;
list<int> x;
x.clear();
while(!stiva.empty())
stiva.pop();
for(i=n;i>=1;i--)
if(!viz[ordine[i]])
{
componente.push_back(x);
nod=ordine[i];
viz[ordine[i]]=1;
dfs();
cate++;
}
fout<<cate<<'\n';
int sum=0;
list<int>::iterator it;
vector<int> vect;
vect.clear();
//for(i=0;i<cate;i++)
//{
//fout<<componente[i].size()<<',';
// sum+=componente[i].size();
// vect.push_back(componente[i].size());
//for(it=componente[i].begin();it!=componente[i].end();it++)
// fout<<*it<<' ';
// }
//fout<<sum<<"\n";
//fout<<"aaaaaaaaaaaaaaaaaaa\n";
//sort(vect.begin(),vect.end(),comp);
//for(i=0;i<100;i++)
// fout<<vect[i]<<endl;
for(i=0;i<cate;i++)
{
for(it=componente[i].begin();it!=componente[i].end();it++)
{
fout<<*it<<' ';
}
fout<<'\n';
}
fin.close();
fout.close();
return 0;
}