Pagini recente » Cod sursa (job #2925967) | Cod sursa (job #321393) | Cod sursa (job #1270181) | Cod sursa (job #2259891) | Cod sursa (job #2855591)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
///sa zicem ca am matrice de adiacenta prima data
//int a[10005][10005];
//void read()
//{ int x, y;
// fin >> n >> m;
// for(int i = 1; i <= m; i ++)
// {
// fin >> x >> y;
// a[x][y] = a[y][x] = 1;
// }
//}
int n, m, nr_comp;
bool vis[100005];
vector < int > L[100005];
void read()
{
int x, y;
fin >> n >> m;
for(int i = 1; i <= m; i ++)
{
fin >> x >> y;
L[x].push_back(y);
L[y].push_back(x);
}
}
void dfs(int k)
{
vis[k] = 1;
for(int i = 0; i < L[k].size(); i ++)
{
if(vis[L[k][i]] == 0)
{
vis[L[k][i]] = 1;
dfs(i);
}
}
}
int main()
{
read();
dfs(1);
nr_comp = 1;
for(int i = 2; i <= n; i ++)
{
if(vis[i] == 0)
{
nr_comp++;
dfs(i);
}
}
fout << nr_comp;
return 0;
}