Pagini recente » Cod sursa (job #2770554) | Cod sursa (job #2798021) | Cod sursa (job #2771509) | Cod sursa (job #1959996) | Cod sursa (job #2879788)
#include <fstream>
#include<vector>
#include <algorithm>
#include <set>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int noduri, muchii, nod1, nod2, conexe;
bool viz[100001];
void dfs(vector <set<int>> & vecini, bool viz[], int start)
{
///fout << "fac dfs pentru nodul " << start <<'\n';
viz[start] = 1;
for (auto i : vecini[start])
if (viz[i-1] == 0)
dfs(vecini, viz, i-1);
}
int main()
{
fin >> noduri >> muchii;
vector<set <int>> vecini;
vecini.assign(noduri, {});
while (muchii)
{
fin >> nod1 >> nod2;
vecini[nod1-1].insert(nod2);
vecini[nod2-1].insert(nod1);
muchii--;
}
/*
for (int j = 0; j < noduri; j++)
{
sort(vecini[j].begin(), vecini[j].end());
if (vecini[j].size())
for (auto i = vecini[j].end()-1; i> vecini[j].begin(); i--)
if (*i == *(i-1))
vecini[j].erase(i);
}*/
/*
for (int j = 0; j < noduri; j++)
{
fout << "Nodul " << j+1 << ": ";
for (auto i : vecini[j])
fout << i << ' ';
fout << '\n';
}*/
for (int j = 0; j < noduri; j++)
{
if (viz[j] == 0)
{
conexe++;
viz[j] = 1;
dfs(vecini, viz, j);
}
}
fout << conexe;
return 0;
}