Pagini recente » Cod sursa (job #2788497) | Cod sursa (job #3277633) | Cod sursa (job #1412896) | Cod sursa (job #2090620) | Cod sursa (job #2809325)
#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<int>L[100001];
bitset<100001>viz;
void DFS(int x)//primesc ca parametru un nod din graf
{
unsigned int i;
int y;
viz[x] = 1;
for(i=0;i<L[x].size();++i)//parcurg lista de vecini ai lui x
{
y = L[x][i];//y este vecin cu x
if(viz[y]==0)//y nu a fost marcat inca
DFS(y);//apelez DFS ca sa il marchez, si marchez si vecinii lui
}
}
int main()
{
int x, y;
ifstream fin("dfs.in");
fin>>N>>M;
for(int i=1;i<=M;++i)
{
fin>>x>>y;
L[x].push_back(y);//in lista de adiacenta (lista de vecini)
//il adaug pe y
L[y].push_back(x);//adaug pe x la lista lui y
}
fin.close();
//am terminat citirea
//acum numaram componentele conexe
int nr_comp_conexe = 0;
for(int i=1;i<=N;++i)
if(viz[i]==0)//am gasit un nod nevizitat
{
DFS(i);
nr_comp_conexe++;
}
ofstream fout("dfs.out");
fout<<nr_comp_conexe<<"\n";
fout.close();
return 0;
}