Pagini recente » Cod sursa (job #2831980) | Cod sursa (job #1693215) | Cod sursa (job #3200173) | Cod sursa (job #517270) | Cod sursa (job #560297)
Cod sursa(job #560297)
#include <fstream>
#include <vector>
using namespace std;
#define maxN 100005
#define PB push_back
int sol, N, M;
vector < int > lista[maxN];
bool cont[maxN];
void vecini (int nod)
{
cont[nod] = true;
for (unsigned int i = 0; i < lista[nod].size(); ++ i)
if ( ! cont[lista[nod][i]] )
vecini ( lista[nod][i] );
}
int main()
{
ifstream f("dfs.in");
ofstream g("dfs.out");
f >> N >> M;
for (int i = 1; i <= M; ++ i)
{
int x, y;
f >> x >> y;
lista[x].PB(y);
lista[y].PB(x);
}
for (int i = 1; i <= N; ++ i)
{
if ( cont[i] )
continue;
cont[i] = true;
for (unsigned int j = 0; j < lista[i].size(); ++ j)
if ( ! cont[lista[i][j]] )
vecini (lista[i][j]);
++ sol;
}
g << sol;
return 0;
}