Pagini recente » Cod sursa (job #384870) | Cod sursa (job #1488639) | Cod sursa (job #18301) | Cod sursa (job #2258848) | Cod sursa (job #979275)
Cod sursa(job #979275)
#include <fstream>
#include <bitset>
#include <vector>
#include <list>
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;
int lider;
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;
}
vector<list<int> > componente;
int cate;
void dfs(int nod)
{
list<int>::iterator it;
componente[cate].push_back(nod);
for(it=v[nod].vecini.begin();it!=v[nod].vecini.end();it++)
if(!viz[*it])
{
viz[*it]=1;
dfs(*it);
}
}
int main()
{
ifstream fin("ctc.in");
ofstream fout("ctc.out");
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();
for(i=n;i>=1;i--)
if(!viz[ordine[i]])
{
componente.push_back(x);
lider=ordine[i];
viz[ordine[i]]=1;
dfs(ordine[i]);
cate++;
}
fout<<cate<<'\n';
list<int>::iterator it;
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;
}