Pagini recente » Cod sursa (job #1092259) | Cod sursa (job #1441556) | Cod sursa (job #306072) | Cod sursa (job #1587918) | Cod sursa (job #1006772)
#include <fstream>
#include <algorithm>
#include <queue>
#define NMAX 100005
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n, m, viz[NMAX], p,i,x,y,a[3][1000010],k,start[100010],j,conex;
queue <int> q;
void dfs(int nod)
{
int p, y;
viz[nod] = 1;
x=start[nod];
while(x!=0)
{
if(viz[a[0][x]]==0)
{
q.push(a[0][x]);
}
x=a[1][x];
}
while(! q.empty())
{
p = q.front();
q.pop();
if(viz[p]==0)
dfs(p);
}
}
int main()
{
fin >> n >> m;
k=0;
for (i = 1; i <= m; i++)
{
fin >> x >> y;
k++;
a[0][k]=y;
a[1][k]=start[x];
start[x]=k;
k++;
a[0][k]=x;
a[1][k]=start[y];
start[y]=k;
}
for(i=1; i<=n; i++)
{
if(viz[i]==0)
{
dfs(i);
conex++;
}
}
fout<<conex;
}