Pagini recente » Istoria paginii utilizator/vladi.baras | Istoria paginii utilizator/radu.ghita | Cod sursa (job #88940) | Monitorul de evaluare | Cod sursa (job #362414)
Cod sursa(job #362414)
#include<cstdio>
#include<iterator>
#include<vector>
#include<stack>
using namespace std;
#define N 100005
#define pb push_back
#define p push
vector<int>a[N],index,llink,cod;
vector<bool>este;
stack<int>s;
vector< vector<int> > rez;
#define Min(a,b) ((a)<(b)?(a):(b))
int ind,n,m;
void citire()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
index.resize(n);
index.assign(n,-1);
este.resize(n);
este.assign(n,false);
llink.resize(n);
int x,y;
for (int i=0; i<m; ++i)
{
scanf("%d%d",&x,&y);
a[x-1].pb(y-1);
}
}
void alg_tarjan(int n)
{
llink[n]=index[n]=ind;
++ind;
s.p(n),este[n]=true;
vector<int>::iterator g=a[n].end();
for (vector<int>::const_iterator it=a[n].begin();it!=g; ++it)
{
if (index[*it]==-1)
{
alg_tarjan(*it);
llink[n]=Min(llink[n],llink[*it]);
}
else
if (este[*it])
{
llink[n]=Min(llink[n],llink[*it]);
}
}
if (index[n]==llink[n])
{
cod.clear();
int nod;
do
{
nod=s.top();
cod.pb(nod);
s.pop(),este[nod]=false;
}
while (nod!=n);
rez.pb(cod);
}
}
void componente()
{
for (int i=0; i<n; ++i)
{
if (index[i]==-1)
alg_tarjan(i);
}
}
void afis()
{
size_t g=rez.size();
printf("%d\n",g);
for (size_t i=0; i<g; ++i)
{
size_t g1=rez[i].size();
for (size_t j=0; j<g1; ++j)
printf("%d ",rez[i][j]+1);
printf("\n");
}
}
int main()
{
citire();
componente();
afis();
}