Pagini recente » Cod sursa (job #2434928) | Cod sursa (job #2280529) | Cod sursa (job #981852) | Cod sursa (job #1615825) | Cod sursa (job #728825)
Cod sursa(job #728825)
#include <fstream>
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
vector <bool> selected;
vector <vector<int> > a(100010);
/*typedef vector<int> lista_adj;
lista_adj a[100010];
*/
void DFS(int node)
{
selected[node]=true;
for (int i=0; i<a[node].size(); i++)
if (selected[a[node][i]]==false) DFS(a[node][i]);
}
int main()
{
int n,m,x,y,i;
ifstream f("dfs.in");
f>>n>>m;
selected.reserve(n+1);
//a.reserve(n+30);
for (i=0; i<m; i++) {
f>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
f.close();
/*for (i=1; i<=n; i++) {
cout<<i<<"---";
for (int j=0; j<a[i].size(); j++)
cout<<a[i][j]<<' ';
cout<<'\n';
}*/
int nr=0;
for (i=0; i<=n; i++)
selected[i]=false;
for (i=1; i<=n; i++)
if (selected[i]==false) {
++nr;
DFS(i);
}
freopen("dfs.out","w",stdout);
printf("%d\n",nr);
return 0;
}