Pagini recente » Statistici popsor razvan-ioan (blue-demon) | Cod sursa (job #850031) | Cod sursa (job #1051415) | Cod sursa (job #271621) | Cod sursa (job #938258)
Cod sursa(job #938258)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define in "dfs.in"
#define out "dfs.out"
#define N 100005
vector <bool> d(N+1, false);
vector <int> LIST[N];
int n, m, sol = 0;
void DFS (int x)
{
d[x] = 1;
for (unsigned i = 0; i < LIST[x].size(); ++i)
if (!d[LIST[x][i]])
DFS (LIST[x][i]);
}
int main ()
{
ifstream fin (in);
fin >> n >> m;
for (int i = 0; i < m; ++i) {
int x, y;
fin >> x >> y;
LIST[x].push_back (y);
LIST[y].push_back (x);
}
fin.close();
for (int i = 1; i <= n; ++i)
sort (LIST[i].begin(), LIST[i].end());
for (int x = 1; x <= n; ++x)
if (!d[x])
sol++, DFS (x);
ofstream fout (out);
fout << sol;
fout.close();
return 0;
}