Pagini recente » Cod sursa (job #284179) | Cod sursa (job #1606289) | Cod sursa (job #124073) | Cod sursa (job #2522747) | Cod sursa (job #715326)
Cod sursa(job #715326)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
long N[100001] = {0};
//vector<int> M[100000];
vector<int> *M;
int main(void)
{
fstream fin("dfs.in",ios::in);
fstream fout("dfs.out",ios::out);
long Noduri,Muchii,i,a,b,Co,k;
M = new vector<int>[100001];
pair<int,int> *c;
fin >> Noduri >> Muchii;
for (i = 0;i < Muchii;i += 1)
{
fin >> a >> b;
M[a].push_back(b);
M[b].push_back(a);
}
Co = 0;
for (k = 1;k <= Noduri;k += 1)
{
if (N[k] <= 0)
{
Co += 1;
queue<pair<int,int> *> q;
q.push(new pair<int,int>(k,Co));
N[k] = Co;
while (q.empty() == 0)
{
c = q.front();
q.pop();
for (i = 0;i < M[c->first].size();i += 1)
{
if (N[M[c->first].at(i)] <= 0)
{
q.push(new pair<int,int>(M[c->first].at(i),Co));
N[M[c->first].at(i)] = Co;
}
}
}
}
}
fout << Co;
fin.close();
fout.close();
return 0;
}