Pagini recente » Cod sursa (job #1875759) | Cod sursa (job #2175951) | Cod sursa (job #1639915) | Cod sursa (job #2500351) | Cod sursa (job #870675)
Cod sursa(job #870675)
#include <fstream>
#define Nmax 100003
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
struct Nod { int v; Nod*urm;};
Nod* l[Nmax], *l2[Nmax], *comp[Nmax];
int post[Nmax],n,m,cnt,x,y;
int viz[Nmax];
void df(int nod)
{
Nod *p;
viz[nod] = 1;
p=l[nod];
while(p)
{
if (viz[p->v]==0) df(p->v);
p=p->urm;
}
post[++post[0]] = nod;
}
void df2(int nod)
{
Nod *p;
viz[nod] = 0;
Nod *q = new Nod;
q->v = nod;q->urm=0;
q->urm = comp[cnt];
comp[cnt] = q;
p=l2[nod];
while(p)
{
if (viz[p->v]==1) df2(p->v);
p=p->urm;
}
}
int main()
{
Nod * q,*p;
f>>n>>m;
for (int i=1;i<=m;++i)
{
f>>x>>y;
q = new Nod;
q->v=y;q->urm=0;
q->urm=l[x];
l[x]=q;
q = new Nod;
q->v=x;q->urm=0;
q->urm=l2[y];
l2[y]=q;
}
for (int i=1;i<=n;++i)
if (viz[i] == 0) df(i);
for (int i=n;i>0;--i)
if (viz[post[i]] == 1) { ++cnt; df2(post[i]); }
g<<cnt<<endl;
for (int i=1;i<=cnt;i++)
{
p=comp[i];
while(p){g<<p->v<<' ';p=p->urm;}
g<<endl;
}
return 0;
}
//#include <fstream>//30p ( probleme-timp si memorie)
//using namespace std;
//ifstream f("ctc.in");
//ofstream g("ctc.out");
//int n, m, nrc, a[4000][4000], suc[4000], pred[4000];
//void df (int nod, int nrc)
//{
// int i;
// suc[nod] = nrc;
// for (i = 1; i <= n; i++)
// if (a[nod][i] == 1 and suc[i] == 0) df(i,nrc);
//}
//
//void dft (int nod,int nrc) //df transpus
//{
// int i;
// pred[nod]=nrc;
// for (i = 1; i <= n; i++)
// if (a[i][nod] == 1 and pred[i] == 0) dft(i,nrc);
//}
//
//int main() {
// int c,i, j, x, y;
// f >> n >> m;
// for (i = 1; i <= m; i++)
// {
// f >> x >> y;
// a[x][y] = 1;
// }
//
//for (i = 1; i <= n; i++)
// if (suc[i]==0)
// {
// nrc++;
// df(i,nrc);
// dft(i,nrc);
// for (j = 1; j <= n; j++)
// if (suc[j]!=pred[j]) suc[j]=pred[j]=0;
// }
// g << nrc << endl;
//
//for (c = 1; c <= nrc; c++)
// {
// for (i = 1; i <= n; i++)
// if(suc[i]==c) g << i << ' ';
// g << endl;
// }
//// for (i = 1; i <= n; i++) g<<suc[i]<<' ';g<<endl;
//// for (i = 1; i <= n; i++) g<<pred[i]<<' ';g<<endl;
// return 0;
//}