Pagini recente » Cod sursa (job #1245751) | Cod sursa (job #1279894) | Cod sursa (job #3254920) | Cod sursa (job #2852783) | Cod sursa (job #1504197)
#include <cstdio>
#include <vector>
using namespace std;
FILE *f = fopen ( "dfs.in" , "r" ) , *g = fopen ( "dfs.out" , "w" );
const int MAX = 100001;
int node1 , node2 , N , M , i , nrComp;
bool vis [ MAX ];
vector <int> edge [ MAX ];
void read()
{
fscanf ( f , "%d %d" , &N , &M );
for ( i = 1 ; i <= M ; i ++ )
{
fscanf ( f , "%d %d" , &node1 , &node2 );
edge [ node1 ] . push_back ( node2 );
edge [ node2 ] . push_back ( node1 );
}
}
void dfs ( int node )
{
vis [ node ] = true;
for ( int i = 0 ; i < edge [ node ] . size() ; i ++ )
if (vis [ edge [ node ] [ i ] ] == false )
dfs ( edge [ node ] [ i ] );
}
int main()
{
read();
for ( i = 1 ; i <= N ; i ++ )
if ( vis [ i ] == false )
{
nrComp ++;
dfs ( i );
}
//print
fprintf ( g , "%d\n" , nrComp );
return 0;
}