Pagini recente » Cod sursa (job #1709006) | Cod sursa (job #129242) | Cod sursa (job #1348183) | Cod sursa (job #2023023) | Cod sursa (job #896817)
Cod sursa(job #896817)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
int N, M, i, j, rez=0;
vector<int> V[100005];
struct nod{
int inf;
nod *next;
};
nod *ha[100005];
void add(nod *&dest, int val)
{
nod *p = new nod;
p->inf = val;
p->next = dest;
dest = p;
}
int VIZ[100005];
void solve2(int now)
{
VIZ[now] = 1;
// for(vector<int>::iterator it=V[now].begin();it!=V[now].end();++it)
// if(!VIZ[*it])
// solve(*it);
nod *p;
/*
for(p=ha[now];p != NULL;p=p->next)
if(!VIZ[p->inf])
solve(p->inf);*/
}
void solve(int now)
{
queue<int> Q;
Q.push(now);
while(!Q.empty())
{
int nod = Q.front();
for(vector<int>::iterator it=V[nod].begin();it!=V[nod].end();++it)
if(!VIZ[*it])
{
Q.push(*it);
VIZ[*it] = 1;
}
Q.pop();
}
}
int main()
{
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
cin>>N>>M;
for(i=1;i<=M;++i)
{
int A, B;
scanf("%d %d", &A, &B);
V[A].push_back(B);
V[B].push_back(A);
// add(ha[A], B);
//add(ha[B], A);
}
for(i=1;i<=N;++i)
if(!VIZ[i])
{
++rez;
solve(i);
}
/*
for(i=1;i<=N;++i)
{
for(nod *p=ha[i];p != NULL;p=p->next)
cout<<p->inf<<" ";
cout<<endl;
}
cout<<endl;*/
cout<<rez<<"\n";
return 0;
}