Pagini recente » Cod sursa (job #1366807) | Cod sursa (job #2293928) | Cod sursa (job #2193266) | Cod sursa (job #1164937) | Cod sursa (job #675744)
Cod sursa(job #675744)
#include <cstdio>
#include <algorithm>
#include <vector>
#define MAXN 100001
using namespace std;
int n, m;
vector<int> g[ MAXN ];
bool vizitat[ MAXN ] = {false};
void read()
{
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
scanf("%d%d", &n, &m);
int u, v;
for(int i = 1; i <= n; ++i)
g[i].push_back(0);
for(int i = 1; i <= m; ++i)
{
scanf("%d%d", &u, &v);
g[ u ].push_back( v );
g[ v ].push_back( u );
}
}
void dfs(int u)
{
vizitat[ u ] = true;
for(size_t i = 1; i < g[ u ].size(); ++i)
if( !vizitat[ g[ u ][ i ] ] )
dfs(g[ u ][ i ]);
}
void solve()
{
int componenteConexe = 0;
for(int i = 1; i <= n; ++i)
if( !vizitat[i] )
{
dfs(i);
++componenteConexe;
}
printf("%d\n", componenteConexe);
}
int main()
{
read();
solve();
return 0;
}