Pagini recente » Cod sursa (job #1295354) | Cod sursa (job #1035446) | Cod sursa (job #1763134) | Cod sursa (job #2931839) | Cod sursa (job #361576)
Cod sursa(job #361576)
#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();
for (i = 1 ; i <= n ; i++)
if (viz[i] == 0) {
c++;
dfs(i);
}
fprintf(g, "%d", c);
fclose(f);
fclose(g);
return 0;
}