Pagini recente » Cod sursa (job #2361037) | Cod sursa (job #1525612) | Cod sursa (job #2741848) | Cod sursa (job #1684018) | Cod sursa (job #2681743)
#include <fstream>
#define DMAX 105
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int A[DMAX][DMAX],viz[DMAX];
struct nod {int info; nod *urm;};
struct stiva{nod *prim;};
void insereaza(stiva &S, int x)
{
nod* nod_nou;
nod_nou=new nod;
nod_nou->info=x;
nod_nou->urm=S.prim;
S.prim=nod_nou;
}
int citeste(stiva S)
{
return S.prim->info;
}
void elimina(stiva &S)
{
nod *q;
q=S.prim;
S.prim=S.prim->urm;
delete(q);
}
void DFS(int nod, int n)
{
stiva S;
int i,j;
S.prim=NULL;
insereaza(S,nod);
while(S.prim!=NULL)
{
j=citeste(S);
elimina(S);
//fout<<j<<' ';
for(i=1;i<=n;i++)
if(A[j][i]==1&&viz[i]==0)
{
viz[i]=1;
insereaza(S,i);
}
}
}
int main()
{
int n,m,X,i,a,b,sol=0;
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>a>>b;
A[a][b]=A[b][a]=1;
}
for(X=1;X<=n;X++)
if(viz[X]==0)
{
viz[X]=1;
DFS(X,n);
sol++;
}
fout<<sol<<'\n';
return 0;
}