Pagini recente » Cod sursa (job #1670508) | Cod sursa (job #1053481) | Borderou de evaluare (job #2772021) | Cod sursa (job #278608) | Cod sursa (job #280363)
Cod sursa(job #280363)
#include<stdio.h>
#include<string.h>
#define nmax 100001
// componente tare conexe
int n,m,
st[nmax], // stiva
ns, // nivel stiva
viz[nmax], // vizitate
cont; // comp conexe
struct nod
{
int drum;
nod *urm;
} *l[nmax] , // graf normal
*lt[nmax]; // graf transpus
void DF1(int);
void DF2(int);
void DF_afis(int);
void add(nod *&inc,int info)
{ // adauga un nod in lista vecinilor
nod *p=new nod;
p->drum=info;
p->urm=inc;
inc=p;
}
int main()
{
int a,b;
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i)
{ // citim muchiile si le adaugam in cele 2 liste
scanf("%d%d",&a,&b);
add(l[a],b);
add(lt[b],a);
}
for(int i=1;i<=n;++i)
if (!viz[i]) // pentru fiecare nod nevizitat
DF1(i); // parcurgem in adancime
memset(viz,0,sizeof(viz)); // reinitializam Viz[]
for(int i=n;i;--i) // pentru fiecare nod din stiva
if (!viz[st[i]])// daca nu e vizitat
{
DF2(st[i]); // parcurgem pe graful transpus
++cont; // numaram nr de comp conexe
//printf("\n");
}
printf("%d\n",cont); // afisam numaru de comp conexe
memset(viz,0,sizeof(viz)); // reinitializam viz[]
for(int i=n;i;--i)// pentru fiecare nod
if (!viz[st[i]])// daca nu e vizitat
{
DF_afis(st[i]); // parcurgem in adancime si afisam nodurile
printf("\n"); // din componenta conexa curenta
}
return 0;
}
void DF1 (int x)
{
nod *p=l[x];// parcurgere in adancime
viz[x]=1; // pe graf normal
for(;p;p=p->urm)
if (!viz[p->drum])
DF1(p->drum);
st[++ns]=x; // punem nodul in stiva in ordine inversa DF
}
void DF2(int x)
{
nod *p=lt[x];
viz[x]=1;
//printf("%d ",x);
for(;p;p=p->urm)
if (!viz[p->drum])
DF2(p->drum);
}
void DF_afis(int x)
{
nod *p=lt[x];
viz[x]=1;
printf("%d ",x);
for(;p;p=p->urm)
if (!viz[p->drum])
DF_afis(p->drum);
}