Pagini recente » Cod sursa (job #2553133) | Cod sursa (job #1767522) | Cod sursa (job #2527789) | Cod sursa (job #1195134) | Cod sursa (job #575565)
Cod sursa(job #575565)
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
int n,indax=1,nrsol=0;
vector<int> a[100001],idx,low,comp;
vector< vector<int> > sol;
vector<bool> instack;
stack<int> s;
void readData(){
int i,m,x,y;
freopen("ctc.in","r",stdin);
scanf("%d %d",&n,&m);
for(i=0;i<m;++i){
scanf("%d %d",&x,&y);
a[x].push_back(y);
}
idx.resize(n+1);
idx.assign(n+1,-1);
low.resize(n+1);
instack.resize(n+1);
instack.assign(n+1,false);
}
void ctc(int x){
idx[x]=low[x]=indax;
++indax;
s.push(x); instack[x]=true;
vector<int>::iterator it;
for(it=a[x].begin();it!=a[x].end();++it)
if(idx[*it]==-1){
ctc(*it);
low[x]=min(low[x],low[*it]);
}
else if(instack[*it])
low[x]=min(low[x],low[*it]);
if(idx[x]==low[x]){
++nrsol;
comp.clear();
int nod;
do{ nod=s.top();
comp.push_back(nod);
s.pop();
instack[nod]=false;
} while(nod!=x);
sol.push_back(comp);
}
}
void writeData(){
unsigned int i,j;
freopen("ctc.out","w",stdout);
printf("%d\n",nrsol);
for(i=0;i<sol.size();++i){
for(j=0;j<sol[i].size();++j)
printf("%d ",sol[i][j]);
printf("\n");
}
}
int main()
{
readData();
for(int i=1;i<=n;++i)
if(idx[i]==-1)
ctc(i);
writeData();
return 0;
}