Pagini recente » Cod sursa (job #292115) | Cod sursa (job #2161600) | Cod sursa (job #13910) | Borderou de evaluare (job #1330594) | Cod sursa (job #1193562)
#include <cstdio>
#include <vector>
#include <climits>
#include <queue>
using namespace std;
#define NMAX 100003
int N,M,i,X,Y,componente;
vector < int > G[NMAX];
queue <int> Q;
bool sel[NMAX];
void DFS(int nod)
{
vector < int > :: iterator it;
Q.push(nod);
sel[nod]=true;
while (!Q.empty())
{
for (it=G[Q.front()].begin();it!=G[Q.front()].end();++it)
{
if (sel[*it]) continue;
sel[*it]=true;
Q.push(*it);
}
Q.pop();
}
}
int main()
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
scanf("%d%d",&N,&M);
for (i=1;i<=M;++i)
{
scanf("%d%d",&X,&Y);
G[X].push_back(Y);
G[Y].push_back(X);
}
for (i=1;i<=N;++i)
{
if (sel[i]) continue;
++componente;
DFS(i);
}
printf("%d\n",componente);
return 0;
}