Pagini recente » Cod sursa (job #322199) | Cod sursa (job #2919052) | Cod sursa (job #644044) | Cod sursa (job #896426) | Cod sursa (job #659104)
Cod sursa(job #659104)
#include <cstdio>
#include <stack>
#include <vector>
using namespace std;
const int MAX_N = 100002;
stack < int > df;
vector < int > edge[ MAX_N ];
int N, M, use[ MAX_N ], nrComp;
void read()
{
int i, x, y;
freopen( "dfs.in", "r", stdin );
scanf( "%d %d", &N, &M );
for( i = 1; i <= M; ++i )
{
scanf( "%d %d", &x, &y);
edge[ x ].push_back( y );
edge[ y ].push_back( x );
}
fclose(stdin);
}
int next_node( int node )
{
int i;
for( i = 0; i < edge[ node ].size(); ++i )
if( ! use[ edge[ node ][ i ] ] )
return edge[ node ][ i ];
return -1;
}
void dfs( int node )
{
int nodec;
df.push( node );
use[ node ] = 1;
while( ! df.empty() )
{
nodec = next_node( df.top() );
if( nodec == -1 )
df.pop();
else
{
df.push( nodec );
use[ nodec ] = 1;
}
}
}
void write()
{
freopen("dfs.out","w",stdout);
printf( "%d\n", nrComp );
fclose(stdout);
}
int main()
{
read();
for( int i = 1; i <= N; ++i )
if( !use[ i ] )
{
nrComp ++;
dfs( i );
}
write();
return 0;
}