Pagini recente » Cod sursa (job #8844) | Cod sursa (job #1748133) | Cod sursa (job #11115) | Cod sursa (job #124495) | Cod sursa (job #2734853)
#include <fstream>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
const int nmax = 100000;
struct vint{
int *v = nullptr;
int capacity = 0, size = 0;
void push_back( int x );
void pop_back( );
void resize( int x );
void resize( int x, int y );
void shrink_to_fit( );
};
void vint::push_back( int x ) {
if ( v == nullptr ) {
v = new int[1];
capacity = 1;
v[0] = x;
size = 1;
} else if ( size == capacity ) {
int *v_aux = new int[capacity*2];
for ( int i = 0; i < size; ++ i ) {
v_aux[i] = v[i];
}
delete[] v;
v = v_aux;
capacity *= 2;
v[size] = x;
++ size;
} else {
v[size] = x;
++ size;
}
}
void vint::pop_back( ) {
if ( size > 0 ) {
--size;
}
}
void vint::resize( int x ) {
if ( size > x ) {
size = x;
} else if ( size < x ) {
if ( capacity < x ) {
int *v_aux = new int[x];
for ( int i = 0; i < size; ++ i ) {
v_aux[i] = v[i];
}
delete[] v;
v = v_aux;
capacity = x;
}
size = x;
}
}
void vint::resize( int x, int y ) {
if ( size > x ) {
size = x;
} else if ( size < x ) {
if ( capacity < x ) {
int *v_aux = new int[x];
for ( int i = 0; i < size; ++ i ) {
v_aux[i] = v[i];
}
delete[] v;
v = v_aux;
capacity = x;
}
for ( int i = size; i < x; ++ i ) {
v[i] = y;
}
size = x;
}
}
void vint::shrink_to_fit( ) {
if ( size < capacity ) {
int *v_aux = new int[size];
for ( int i = 0; i < size; ++ i ) {
v_aux[i] = v[i];
}
delete[] v;
v = v_aux;
capacity = size;
}
}
vint g[nmax+1];
bool u[nmax+1];
void dfs( int x ) {
u[x] = 1;
for ( int i = 0; i < g[x].size; ++ i ) {
int xn = g[x].v[i];
if ( u[xn] == 0 ) {
dfs(xn);
}
}
}
int main( ) {
int n, 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);
}
for ( int i = 1; i <= n; ++ i ) {
g[i].shrink_to_fit();
}
int sol = 0;
for ( int i = 1; i <= n; ++ i ) {
if ( u[i] == 0 ) {
++ sol;
dfs(i);
}
}
fout << sol << "\n";
return 0;
}