Pagini recente » Istoria paginii utilizator/dafinatrufas | Profil NuSuntRoman | Istoria paginii blog/oji-oni-2005 | Monitorul de evaluare | Cod sursa (job #361574)
Cod sursa(job #361574)
#include<fstream.h>
#include<vector>
#define Nmax 100010
using namespace std;
vector <int> A[Nmax];
int c, n, m, i, x, y, ok, start;
int viz[Nmax], Lg[Nmax];
void dfs(int k){
int j;
viz[k] = c;
for (j = 0 ; j <= Lg[k] - 1 ; j++)
if (viz[A[k][j]] == 0)
dfs(A[k][j]);
}
int main(){
FILE *f = fopen ("dfs.in","r");
FILE *g = fopen ("dfs.out","w");
fscanf (f, "%d %d", &n, &m);
for (i = 1 ; i <= m ; i++){
fscanf(f, "%d %d", &x, &y);
A[x].push_back(y);
A[y].push_back(x);
}
ok = 1;
for (i = 1 ; i <= n ; i++)
Lg[i] = A[i].size();
while (ok){
ok = 0;
for (i = 1 ; i <= n ; i++)
if (viz[i] == 0) {
ok = 1;
c++;
start = i;
break;
}
dfs(start);
}
fprintf(g, "%d", c);
fclose(f);
fclose(g);
return 0;
}