Pagini recente » Cod sursa (job #2051816) | Cod sursa (job #389735) | Cod sursa (job #375190) | Cod sursa (job #210771) | Cod sursa (job #1849206)
// Componente tare conexe - alg. Kosaraju-Sharir -. O(n+m)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("ctc.in");
ofstream g ("ctc.out");
struct nod
{
int inf;
nod *urm;
} *l[101], *lt[101];
int n, viz[101], st[101], k;
void adaug (nod *&l, int x)
{ nod *c;
c=new nod;
c->inf=x;
c->urm=l;
l=c;
}
void DF1(int i)
{
nod *c;
viz[i]=1;
for(c=l[i];c!=NULL;c=c->urm)
if (!viz[c->inf]) DF1(c->inf);
st[++k]=i;
}
void DF2(int i)
{
nod *c;
viz[i]=1;
for(c=lt[i];c!=NULL;c=c->urm)
if (!viz[c->inf]) DF2(c->inf);
}
void DF2afij(int i)
{
nod *c;
viz[i]=1; g<<i<<" ";
for(c=lt[i];c!=NULL;c=c->urm)
if (!viz[c->inf]) DF2afij(c->inf);
}
int main()
{ int i, x, y, m, nr=0;
f>>n >> m;
while (f>>x>>y)
{ adaug(l[x],y);
adaug(lt[y],x);
}
for (i=1; i<=n; i++)
if (!viz[i]) DF1(i);
memset (viz,0, sizeof(viz));
for (i=n; i>=1;i--)
if (!viz[st[i]])
{ nr++,DF2(st[i]);
}
g << nr << '\n';
for(i=1;i<=n;i++)viz[i]=0;
for (i=1; i<=n; i++)
if (!viz[i]) DF1(i);
memset (viz,0, sizeof(viz));
for (i=n; i>=1;i--)
if (!viz[st[i]])
{ DF2afij(st[i]);
g<<'\n';
}
g.close();
return 0;
}