Pagini recente » Cod sursa (job #360750) | Cod sursa (job #677903) | Cod sursa (job #1141163) | Cod sursa (job #1622611) | Cod sursa (job #1024808)
#include <stdio.h>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#define IN "dfs.in"
#define OUT "dfs.out"
#define NMAX 100005
int viz[NMAX],n,m,componente;
vector<int> graf[NMAX];
stack<int> stiva;
void citire();
void rezolvare();
void afisare();
int main()
{
citire();
rezolvare();
afisare();
return 0;
}
void citire()
{
FILE * fin=fopen(IN,"r");
int i,x,y;
fscanf(fin,"%d%d",&n,&m);
for(i=1;i<=m;i++)
{
fscanf(fin,"%d%d",&x,&y);
graf[x].push_back(y);
graf[y].push_back(x);
}
fclose(fin);
}
void rezolvare()
{
int contor,element,z,y,i;
for(contor=1;contor<=n;contor++)
{
if(viz[contor]==0)
{
componente++;
stiva.push(contor);
viz[contor]=1;
while(!stiva.empty())
{
element=stiva.top();
y=-1;
for(i=0;i<graf[element].size();i++)
{
z=graf[element][i];
if(viz[z]==0)
{
viz[z]=1;
stiva.push(z);
y=1;
break;
}
}
if(y==-1)
stiva.pop();
}
}
}
}
void afisare()
{
FILE * fout=fopen(OUT,"w");
fprintf(fout,"%d\n",componente);
fclose(fout);
}