Pagini recente » Cod sursa (job #213693) | Cod sursa (job #1393957) | Cod sursa (job #2433526) | Cod sursa (job #2930112) | Cod sursa (job #1761704)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
vector <int> vec[100002];
vector <int>::iterator ii;
queue <int> st;
int m,n,unused[100002];
int main()
{
ifstream fin ("dfs.in");
ofstream fout ("dfs.out");
fin>>n>>m;
int i,x,y;
memset(unused,0,sizeof(unused));
for(i=0; i<m; ++i)
{
fin>>x>>y;
vec[x].push_back(y);
vec[y].push_back(x);
}
x=0,y=1;///x=nr de elem conexe
while(y<=n)
{
++x;
st.push(y);
unused[y]=1;
while(!st.empty())
{
int a=st.front();
st.pop();
ii=vec[a].begin();
while(ii!=vec[a].end())
{
if(!unused[*ii])
unused [*ii]=1,st.push(*ii);
++ii;
}
}
while(unused[y])++y;
}
fout<<x;
return 0;
}