Pagini recente » Cod sursa (job #1064495) | Cod sursa (job #129453) | Cod sursa (job #435192) | Cod sursa (job #72498) | Cod sursa (job #984200)
Cod sursa(job #984200)
#include <iostream>
#include <fstream>
using namespace std;
#define Nmax 100005
int *G[Nmax];
int degree[Nmax];
int viz[Nmax];
int N, M;
void read()
{
fstream f;
f.open( "dfs.in", ios::in );
f >> N >> M;
for ( int i = 1, a, b; i <= M; ++i )
{
f >> a >> b;
degree[a]++;;
degree[b]++;
}
f.close();
f.open( "dfs.in", ios::in );
f >> N >> M;
for ( int i = 1; i <= N; degree[i++] = 0 )
G[i] = new int[degree[i] + 1];
for ( int i = 1, a, b, c; i <= M; ++i )
{
f >> a >> b;
G[a][ degree[a]++ ] = b;
G[b][ degree[b]++ ] = a;
}
for ( int i = 1; i <= N; i++ )
{
G[i][degree[i]] = -1;
degree[i] = 0;
}
f.close();
}
void DFS( int nod )
{
viz[nod] = 1;
for ( int *p = G[nod]; *p != -1; p++ )
if ( !viz[ *p ] )
DFS( *p );
}
void solve()
{
ofstream g("dfs.out");
int s = 0;
for ( int i = 1; i <= N; ++i )
if ( !viz[i] )
{
s++;
DFS( i );
}
g << s << "\n";
g.close();
}
int main()
{
read();
solve();
return 0;
}