Pagini recente » Cod sursa (job #2188440) | Cod sursa (job #2702068) | Cod sursa (job #202557) | Cod sursa (job #1858066) | Cod sursa (job #627157)
Cod sursa(job #627157)
#include <fstream>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
struct node
{
int nr;
node *next;
} *v[100005],*p/*comp[100005]*/;
int n,m,a,b,st[100005],index[100005],lowlink[100005],k,lvl,c;
char prez[100005];
vector <int> aux;
vector <int> :: iterator it, o;
vector < vector<int> > comp;
inline int MINIM(int a, int b) {return (a<b)?a:b;}
void ctc(int i)
{
node *q;
index[i]=++k;
lowlink[i]=k;
st[++lvl]=i;
prez[i]='1';
q=v[i];
while(q)
{
if(!index[q->nr])
{
ctc(q->nr);
lowlink[i]=MINIM(lowlink[i],lowlink[q->nr]);
}
else if(prez[q->nr]) lowlink[i]=MINIM(lowlink[i],index[q->nr]);
q=q->next;
}
if(lowlink[i]==index[i])
{
++c;
aux.clear();
while(st[lvl]!=i)
{
/*p=new node;
p->nr=st[lvl];
p->next=comp[c];
comp[c].nr=st[lvl];*/
aux.push_back (st[lvl]);
prez[st[lvl]]='\0';
--lvl;
}
/*p=new node;
p->nr=i;
p->next=comp[c];
comp[c]=p;*/
aux.push_back (i);
comp.push_back (aux);
prez[i]='\0';
--lvl;
}
}
int main()
{
int i;
f>>n>>m;
for(i=1;i<=m;++i)
{
f>>a>>b;
p=new node;
p->nr=b;
p->next=v[a];
v[a]=p;
}
for(i=1;i<=n;++i)
if(!index[i]) ctc(i);
g<<c<<'\n';
/*for(i=1;i<=c;++i)
{
p=comp[i];
while(p) g<<p->nr<<' ', p=p->next;
g<<'\n';
}*/
for(i=0;i<c;++i)
{
o=comp[i].end();
for(it=comp[i].begin(); it!=o; ++it) g<<*it<<' ';
g<<'\n';
}
f.close(); g.close();
return 0;
}