Pagini recente » Cod sursa (job #1597424) | Cod sursa (job #2149737) | Cod sursa (job #1343643) | Cod sursa (job #1436031) | Cod sursa (job #868288)
Cod sursa(job #868288)
#include<cstdio>
#include<algorithm>
#include<iterator>
#include<stack>
#include<vector>
using namespace std ;
vector <int> list[100003],a ; //listele de adiacenta
stack <int> s; //stiva din algoritm
vector <vector < int> > ctc; //vector de vectori de componete tare conexe
int ind,n,m,x,y,index[100003],lowlink[100003],in_stiva[100003];
int min(int a,int b)
{
if (a<=b) return a;
else return b;
}
void afisare(vector< vector < int> > ctc)
{
int i;
printf("%d\n",ctc.size());
vector<int>a;
vector<int>::iterator it ;
for(i=0;i<ctc.size();i++)
{
a=ctc[i];
for(it=a .begin();it<a.end();it++)
printf("%d ",*it);
printf("\n");
}
}
void tarjan( int v )
{
index[v]= ind ;
lowlink[v]= ind ;
ind++;
s.push(v) ;
in_stiva[v]= 1;
vector < int >::const_iterator it ;
for(it=list[v].begin();it<list[v].end();it++)
{
if (index[*it]==0)
{
tarjan(*it);
lowlink[v]=min(lowlink[v],lowlink [*it]);
}
else
if (in_stiva[*it]!=0) lowlink[v]=min(lowlink[v],index[*it]);
}
if( lowlink[v]==index[v])
{
int aux ;
a.clear();
do
{
a.push_back(aux=s.top());
in_stiva[aux]=0;
s.pop();
}
while(v!=aux);
ctc.push_back(a);
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
list[x].push_back(y);
}
ind=1;
for(int i=1;i<=n;i++)
if(index[i]==0)tarjan(i);
afisare(ctc);
return 0;
}