Pagini recente » Cod sursa (job #2708730) | Cod sursa (job #1831739) | Cod sursa (job #456973) | Cod sursa (job #2566860) | Cod sursa (job #979425)
Cod sursa(job #979425)
#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[100005];
bitset<100005> viz;
bitset<100005> viz_rev;
int ordine[100005];
int termin;
stack<pair<int,int> > stiva;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
/*
void dfs_rev(int nod)
{
list<int>::iterator it;
stiva.push(make_pair(nod,0));
//fout<<"ADAUGAT "<<nod<<','<<0<<'\n';
pair<int,int> curent;
while(!stiva.empty())
{
curent=stiva.top();
if(curent.second==1)
{
ordine[termin++]=curent.first;
//fout<<"ORDINE["<<termin-1<<"]="<<curent.first<<'\n';
// fout<<"SCOS "<<curent.first<<','<<curent.second<<'\n';
stiva.pop();
continue;
}
stiva.top().second=1;
//fout<<"MODIFICAT "<<stiva.top().first<<','<<stiva.top().second<<'\n';
for(it=v[curent.first].vecini_rev.begin();it!=v[curent.first].vecini_rev.end();it++)
if(!viz_rev[*it])
{
viz_rev[*it]=1;
stiva.push(make_pair(*it,0));
// fout<<"ADAUGAT "<<*it<<','<<0<<'\n';
}
}
}//*/
vector<list<int> > componente;
int cate;
void dfs(int nod)
{
list<int>::iterator it;
stiva.push(make_pair(nod,0));
int curent;
while(!stiva.empty())
{
curent=stiva.top().first;
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(make_pair(*it,0));
}
}
}
/*
void dfs(int nod)
{
componente[cate].push_back(nod);
list<int>::iterator it;
for(it=v[nod].vecini.begin();it!=v[nod].vecini.end();it++)
if(!viz[*it])
{
viz[*it]=1;
dfs(*it);
}
}//*/
void dfs_rev(int nod)
{
list<int>::iterator it;
for(it=v[nod].vecini_rev.begin();it!=v[nod].vecini_rev.end();it++)
if(!viz_rev[*it])
{
viz_rev[*it]=1;
dfs_rev(*it);
}
ordine[termin++]=nod;
}
int main()
{
cate=0;
int n,m,i,a,b;
fin>>n>>m;
for(i=0;i<m;i++)
{
fin>>a>>b;
v[a].vecini.push_back(b);
v[b].vecini_rev.push_back(a);
}
termin=1;
for(i=1;i<=n;i++)
if(!viz_rev[i])
{
viz_rev[i]=1;
dfs_rev(i);
}
//cout<<"pas 1 gata"<<endl;
list<int> x;
x.clear();
while(!stiva.empty())
stiva.pop();
for(i=n;i>=1;i--)
{
//fout<<"ordine["<<i<<"]="<<ordine[i]<<'\n';
if(!viz[ordine[i]])
{
// fout<<"DA\n";
componente.push_back(x);
viz[ordine[i]]=1;
dfs(ordine[i]);
cate++;
}
}
fout<<cate<<'\n';
list<int>::iterator it;
vector<int> vect;
vect.clear();
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;
}