Pagini recente » Cod sursa (job #2071061) | Cod sursa (job #922250) | Cod sursa (job #56592) | Cod sursa (job #1631695) | Cod sursa (job #1003671)
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
//defines
#define NMax 100001
#define For(i,a,b) for(long i=a;i<=b;i++)
#define scan scanf
//stl defines
#define V vector<long>
#define Q queue<long>
#define IFor(i,a) for(V::iterator i=a.begin();i<a.end();i++)
#define pb push_back
#define pf pop_front
#define viz(a) viz[a]=1
//variables
V v[NMax];
long n,m,x,y,count;
bool viz[NMax];
//breadth-first search(BFS)
void bfs(long now) {
Q q;
q.push(now);viz(now);
while(!q.empty()) {
now=q.front(); //get next element in q
IFor(i,v[now]) //for each connected vertex
if(!viz[*i])
q.push(*i), //add element to q
viz(*i);
q.pop(); //remove front(current) element in q
}
}
//deep-first search
void dfs(long now) {
viz(now);
IFor(i,v[now]) //for each connected vertex
if(!viz[*i])
dfs(*i);
}
//main
int main()
{
freopen("dfs.in","rt",stdin);
freopen("dfs.out","wt",stdout);
scan("%ld %ld",&n,&m);
For(i,1,m)
scan("%ld %ld",&x,&y),
v[x].pb(y),
v[y].pb(x);
For(i,1,n)
if(!viz[i])
dfs(i),count++;
printf("%ld\n",count);
return 0;
}