Pagini recente » Diferente pentru blog/valorificarea-spiritului-competitiv intre reviziile 9 si 8 | Istoria paginii utilizator/dorusarmasan | Istoria paginii utilizator/victorcara26 | Statistici Maria Cellsia Zemora (marriAz) | Cod sursa (job #821491)
Cod sursa(job #821491)
#include<iostream>
#include<fstream>
using namespace std;
#define NMAX 100001
struct nod {
int info;
nod *urm;
};
typedef nod* PNOD;
PNOD v[NMAX],vt[NMAX];
int suc[NMAX],pred[NMAX],nc,n;
void adauga(PNOD &p, int y)
{
PNOD aux;
aux=new nod;
aux->urm=p;
aux->info=y;
p=aux;
}
void citire()
{
int m,x,y,i;
ifstream f("ctc.in");
f>>n>>m;
for(i=1;i<=m;i++) {
f>>x>>y;
adauga(v[x],y);
adauga(vt[y],x);
}
f.close();
}
void dfs(int nod)
{
suc[nod]=nc;
for(PNOD p=v[nod];p!=NULL;p=p->urm)
if(suc[p->info]==0)
dfs(p->info);
}
void dfst(int nod)
{
pred[nod]=nc;
for(PNOD p=vt[nod];p!=NULL;p=p->urm)
if(pred[p->info]==0)
dfst(p->info);
}
int main ()
{
int i,j;
citire();
ofstream g("ctc.out");
for(i=1;i<=n;i++)
if(suc[i]==0) {
nc++;
suc[i]=nc;
dfs(i);
dfst(i);
for(j=1;j<=n;j++)
if(suc[j]!=pred[j])
suc[j]=pred[j]=0;
}
g<<nc<<'\n';
for(i=1;i<=nc;i++) {
for(j=1;j<=n;j++)
if(suc[j]==i)
g<<j<<" ";
g<<'\n';
}
g.close();
return 0;
}