Pagini recente » Cod sursa (job #574566) | Cod sursa (job #2856437) | Cod sursa (job #746288) | Cod sursa (job #1410231) | Cod sursa (job #1649829)
#define lmax 110
#include <iostream>
#include <vector>
#include <stack>
#include <cstdio>
using namespace std;
int index[lmax],lowlink[lmax],idx=0,nctc=0,epestiva[lmax];
vector<int> lv[lmax];
vector<int> ctcc[lmax];
stack<int> st;
void ctc(int i)
{
vector<int>:: iterator ii;
++idx;
st.push(i);epestiva[i]=1;
lowlink[i]=index[i]=idx;
for(ii=lv[i].begin();ii!=lv[i].end();++ii)//arcul este (i,*ii)
if(!index[*ii])
{
ctc(*ii);
//la intoarcere ii fac update lu' lowlinku' astuia pe care sunt
lowlink[i]=min(lowlink[i],lowlink[*ii]);
}
else
if(epestiva[*ii])
lowlink[i]=min(lowlink[*ii],lowlink[i]);
if(lowlink[i]==index[i])
{
++nctc;
//scot de pe stiva pina dau de i shi le bag in vector
while(st.top()!=i)
{
ctcc[nctc].push_back(st.top());
epestiva[st.top()]=0;
st.pop();
}
ctcc[nctc].push_back(st.top());
epestiva[st.top()]=0;st.pop();
}
}
int main()
{
FILE *f=fopen("ctc.in","r");
int n,m,i,j,x,y;
fscanf(f,"%d%d",&n,&m);
for(i=1;i<=m;i++)
{
fscanf(f,"%d%d",&x,&y);
lv[x].push_back(y);
}
for(i=1;i<=n;i++)
if(!index[i])
ctc(i);
fclose(f);
f=fopen("ctc.out","w");
fprintf(f,"%d\n",nctc);
vector<int>::iterator ii;
for(i=1;i<=nctc;i++)
{
for(ii=ctcc[i].begin();ii!=ctcc[i].end();++ii)
fprintf(f,"%d ",*ii);
fprintf(f,"\n");;
}
return 0;
}