Pagini recente » Cod sursa (job #170218) | Cod sursa (job #1282201) | Cod sursa (job #974850) | Cod sursa (job #1892238) | Cod sursa (job #1694832)
# include <fstream>
# include <algorithm>
# include <queue>
# include <vector>
# define SIZE 100005
using namespace std;
ifstream f ( "dfs.in" );
ofstream g ( "dfs.out" );
class Graf {
int n, m;
bool v[SIZE];
vector < vector < int > > A;
public:
Graf() {};
~Graf() {};
void read();
void set_viz();
void DFS( int start );
void solve();
};
void Graf :: read() {
f >> n >> m;
A.resize( n + 1 );
for ( int i = 0; i < n; ++ i ) {
int x, y; f >> x >> y;
A[x].push_back( y );
A[y].push_back( x );
}
}
void Graf :: set_viz() {
for ( int i = 0; i <= SIZE; ++ i ) {
v[i] = false;
}
}
void Graf :: DFS( int start ) {
v[start] = true;
for ( auto it: A[start] ) {
if ( v[it] == 0 ) {
DFS( it );
}
}
}
void Graf :: solve() {
read();
set_viz();
int answer = 0;
for ( int nod = 1; nod <= n; ++ nod ) {
if ( v[nod] == 0 ) {
++ answer;
DFS( nod );
}
}
g << answer;
}
int main()
{
Graf G;
G.solve();
return 0;
}