Pagini recente » Cod sursa (job #226387) | Cod sursa (job #3030251) | Cod sursa (job #1485537) | Cod sursa (job #240124) | Cod sursa (job #1390977)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("dfs.in"); ofstream g("dfs.out");
int i,j,n,m,s,a,b,now,z,p,d[100010];
vector <int> v[100010];
queue <int> q;
int main()
{ f>>n>>m;
for(i=1;i<=m;i++) {f>>a>>b; v[a].push_back(b); v[b].push_back(a);}
for(j=1;j<=n;j++)
{ if(d[j]==0)
{ q.push(j); p++; d[j]=p;
while(!q.empty())
{ now=q.front();
z=v[now].size();
for(i=0;i<z;i++)
if(d[v[now][i]]==0)
{ d[v[now][i]]=p;
q.push(v[now][i]);
}
q.pop();
}
}
}
g<<p; g.close(); return 0;
}