Pagini recente » Cod sursa (job #1699786) | Cod sursa (job #2054679) | Cod sursa (job #1308615) | Cod sursa (job #767205) | Cod sursa (job #2990352)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
#define nmax 100001
vector <int> a[nmax];
queue <int> coada;
int viz[nmax];
int n,m,i,j,k1,k2,nr,nodcurent,vecin;
void dfs()
{
int q=1;
while(q<=n)
{
while(viz[q]!=0)
q++;
if(q<=n)
{
nr++;
coada.push(q);
while(coada.empty()==0)
{
nodcurent=coada.front();
viz[nodcurent]=nr;
for(unsigned int i=0;i<a[nodcurent].size();i++)
{
vecin=a[nodcurent][i];
if(viz[vecin]==0)
{
coada.push(vecin);
viz[vecin]=nr;
}
}
coada.pop();
}
}
}
}
int main()
{
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>k1>>k2;
a[k1].push_back(k2);
a[k2].push_back(k1);
}
dfs();
g<<nr;
return 0;
}