Pagini recente » Cod sursa (job #328933) | Cod sursa (job #493601) | Cod sursa (job #99691) | Cod sursa (job #718958) | Cod sursa (job #1332502)
#include <cstdio>
#include <vector>
#define DMAX 100001
using namespace std;
vector <int> A[DMAX];
int C[DMAX];
int n, m, nrc;
bool viz[DMAX];
void citire();
void BFS(int);
void afisare();
int main()
{
int i;
citire();
for (i=1; i<=n; ++i)
if (!viz[i])//face parte din alta parte conexa
BFS (i);
afisare();
return 0;
}
void citire()
{
int i, x, y;
FILE*fin=fopen ("dfs.in", "r");
fscanf(fin, "%d %d", &n, &m);
for (i=1; i<=m; ++i)
{
fscanf(fin, "%d %d", &x, &y);
A[x].push_back(y);
A[y].push_back(x);
}
fclose(fin);
return;
}
void BFS (int vf_start)
{
int prim, ultim, p, i;
C[1]=vf_start; viz[vf_start]=true;//l-am vizitat
++nrc;
prim=ultim=1;
while (prim<=ultim)
{
//extrag un element din coada
p=C[prim++];
//vizitez toti vecinii lui p
for (i=0; i<A[p].size(); ++i)
if (!viz[A[p][i]])
{
viz[A[p][i]]=true;
C[++ultim]=A[p][i];
}
}
return;
}
void afisare()
{
FILE*fout=fopen ("dfs.out", "r");
fprintf(fout, "%d\n", nrc);
fclose(fout);
return;
}