Pagini recente » Cod sursa (job #1234485) | Cod sursa (job #1430177) | Cod sursa (job #482901) | Cod sursa (job #2917425) | Cod sursa (job #2044095)
#include<fstream>
#include<vector>
#include<cstring>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
vector <int> G[100003];
int visit[100003],coada[100003];
void citire(int &n,int &m)
{
fin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
fin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
}
void BFS(int nod)
{
int l=1,r=1;
coada[1]=nod;
while(l<=r)
{
for(int j=0;j<G[coada[l]].size();j++)
if(visit[G[coada[l]][j]]==0)
{
visit[G[coada[l]][j]]=1;
r++;
coada[r]=G[coada[l]][j];
}
l++;
}
}
int main()
{
int n,m,sol=0;
citire(n,m);
for(int i=1;i<=n;i++)
if(visit[i]==0)
{
BFS(i);
sol++;
}
fout<<sol;
}