Pagini recente » Cod sursa (job #273489) | Cod sursa (job #1987595) | Cod sursa (job #2850488) | Cod sursa (job #1670050) | Cod sursa (job #1753237)
#include <stdio.h>
#include <stdlib.h>
typedef struct lista
{
int nod;
struct lista *next;
} *lista;
typedef struct stiva
{
int inf;
struct stiva *next;
} *stiva;
stiva prim;
lista l[100105];
int test,count;
int ok[100105]; //e initializat cu 0
int n,m;
void citire()
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
scanf("%d %d",&n,&m);
int i,x,y;
lista nou;
for (i=1; i<=m; i++)
{
scanf("%d %d",&x,&y);
nou=calloc(1,sizeof(lista));
nou->nod=y;
nou->next=l[x];
l[x]=nou;
nou=calloc(1,sizeof(lista));
nou->nod=x;
nou->next=l[y];
l[y]=nou;
}
}
void afisare()
{
int i;
for (i=1; i<=n; i++)
{
printf("%d : ",i);
lista p;
p=l[i];
while (p)
{
printf("%d, ",p->nod);
p=p->next;
}
printf("\n");
}
}
pune_in_stiva(int nod)
{
stiva nou;
nou=calloc(1,sizeof(stiva));
nou->inf=nod;
nou->next=prim;
prim=nou;
}
scoate_din_stiva()
{
stiva aux;
aux=prim;
prim=prim->next;
free(aux);
}
void afisare_stiva()
{
stiva aux;
aux=prim;
while (aux)
{
printf("%d ",aux->inf);
aux=aux->next;
}
printf("\n");
}
void dfs(int nod)
{
lista p;
if (prim!=NULL)
{
p=l[nod];
while (p)
{
if (ok[p->nod]==0)
{
ok[p->nod]=1;
pune_in_stiva(p->nod);
dfs(p->nod);
}
p=p->next;
}
ok[nod]=2;
/*
afisare_stiva();
printf("hai :");
afisare_rezultat();
printf("\n");
getch();
*/
scoate_din_stiva();
}
}
void afisare_rezultat()
{
int i;
for (i=1; i<=n; i++)
{
printf("%d ",ok[i]);
}
}
void rezolvare()
{
int i=1;
while (i<=n)
{
if (l[i]!=NULL)
{
test=i;
ok[test]=1;
pune_in_stiva(test);
dfs(test);
}
else
{
ok[i]=2;
}
//afisare_rezultat();
//printf("\n");
//getch();
count++;
while (ok[i])
i++;
}
}
int main()
{
citire();
//afisare();
count=0;
rezolvare();
printf("%d",count);
return 0;
}