Pagini recente » Cod sursa (job #1288503) | Cod sursa (job #1274826) | Cod sursa (job #1039513) | Cod sursa (job #2912033) | Cod sursa (job #1724570)
#include<stdio.h>
#include<vector>
FILE *in, *out;
using namespace std;
struct nod
{
int val = 1;
vector<int> muchii;
};
nod graf[100001];
void dfs(int nodo)
{
for(vector<int>::iterator it = graf[nodo].muchii.begin(); it != graf[nodo].muchii.end(); it++) {
if(graf[*it].val == 1) {
graf[*it].val = 0;
dfs(*it);
}
}
}
int main ()
{
int n, m, i, conex, a, b;
in = fopen("dfs.in", "r");
out = fopen("dfs.out", "w");
fscanf(in, "%d%d", &n, &m);
for(i = 0; i < m; i++) {
fscanf(in, "%d%d", &a, &b);
graf[a].muchii.push_back(b);
graf[b].muchii.push_back(a);
}
conex = 0;
for(i = 1; i <= n; i++) {
if(graf[i].val == 1) {
dfs(i);
conex++;
}
}
fprintf(out, "%d", conex);
fclose(in);
fclose(out);
return 0;
}