Pagini recente » Cod sursa (job #175899) | Cod sursa (job #270641) | Cod sursa (job #2069436) | Cod sursa (job #173190) | Cod sursa (job #511822)
Cod sursa(job #511822)
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <stack>
#include <vector>
#define NMAX 100001
using namespace std;
int n,in=1,viz[NMAX],nr;
stack <int> S;
vector < vector <int> > C;
vector <int> c;
struct nod{
int inf;
nod *urm;
};
nod *G[NMAX];
struct comp{
int index,lowlink;
};
comp v[NMAX];
ofstream g("ctc.out");
void add(int x,int y)
{
nod *aux=new nod;
aux->inf=y;
aux->urm=G[x];
G[x]=aux;
}
void citire()
{
int m;
freopen ("ctc.in","r",stdin);
scanf ("%d%d",&n,&m);
int x,y;
for (int i=1;i<=m;i++)
{
scanf ("%d%d",&x,&y);
add(x,y);
}
}
void tarjan (int t)
{
v[t].index=in;
v[t].lowlink=in;
in++;
S.push(t);viz[t]=1;
for (nod *p=G[t];p;p=p->urm)
{
if (!v[p->inf].index)
{
tarjan(p->inf);
v[t].lowlink=min(v[t].lowlink,v[p->inf].lowlink);
}
else
if (viz[p->inf])
v[t].lowlink=min(v[t].lowlink,v[p->inf].index);
}
int x;
if (v[t].index==v[t].lowlink)
{
c.clear();
do{
x=S.top();
S.pop();
c.push_back(x);
}while (t!=x);
C.push_back(c);
}
}
void afis()
{
citire();
for (int i=1;i<=n;i++)
if (!v[i].index)
tarjan(i);
g<<C.size()<<"\n";
for (int i=0;i<C.size();i++)
{
for (int j=0;j<C[i].size();j++)
g<<C[i][j]<<" ";
g<<"\n";
}
}
int main()
{
afis();
return 0;
}