Pagini recente » Cod sursa (job #703539) | Cod sursa (job #737555) | Cod sursa (job #2675673) | Cod sursa (job #1025939) | Cod sursa (job #1125652)
#include <fstream>
#include <algorithm>
#include <vector>
#include <algorithm>
#define MAX_SIZE 100005
using namespace std;
typedef vector < int > ::iterator vii;
ifstream in ( "dfs.in" );
ofstream out ( "dfs.out" );
vector < int > G[MAX_SIZE] ;
int N ,M ,ccount;
bool used[MAX_SIZE];
void DepthFirstSearch ( int node )
{
used[node] = true ;
for( vii it = G[node].begin() ; it != G[node].end() ; ++it )
if ( !used[*it] )
DepthFirstSearch ( *it );
}
int main ( void )
{
int i , j , x , y;
in >> N >> M ;
for ( i = 1 ; i <= M ; ++i )
{
in >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
for ( i = 1 ; i <= N ; ++i )
if ( !used[i] )
DepthFirstSearch( i ) , ++ccount;
out << ccount << "\n";
in.close();
out.close();
return 0 ;
}