Pagini recente » Cod sursa (job #2979794) | Cod sursa (job #1345688) | Cod sursa (job #1612325) | Cod sursa (job #2535219) | Cod sursa (job #710063)
Cod sursa(job #710063)
//Include
#include <stdio.h>
#include <vector>
using namespace std;
//Constante
const int MAX_SIZE = 100001;
//Functii
void dfs(int start);
//Variabile
FILE *in, *out;
int nrNoduri, nrMuchii;
int componente;
vector<int> vizitat;
vector<int> graf[MAX_SIZE];
//Main
int main()
{
in = fopen("dfs.in","rt");
out = fopen("dfs.out","wt");
fscanf(in, "%d%d", &nrNoduri, &nrMuchii);
vizitat.resize(nrNoduri+1);
int cFrom, cTo;
for(int i=1 ; i <=nrMuchii ; ++i)
{
fscanf(in, "%d%d", &cFrom, &cTo);
graf[cFrom].push_back(cTo);
graf[cTo].push_back(cFrom);
}
for(int i=1 ; i <=nrNoduri ; ++i)
if(!vizitat[i])
{
dfs(i);
++componente;
}
fprintf(out, "%d", componente);
fclose(in);
fclose(out);
return 0;
}
void dfs(int start)
{
vizitat[start] = true;
vector<int>::iterator it, end;
end=graf[start].end();
for(it=graf[start].begin() ; it!=end ; ++it)
if(!vizitat[*it])
dfs(*it);
}