Pagini recente » Cod sursa (job #815293) | Cod sursa (job #2354284) | Cod sursa (job #646697) | Cod sursa (job #495338) | Cod sursa (job #926999)
Cod sursa(job #926999)
#include<cstdio>
#include<vector>
#include<cstdlib>
using namespace std;
#define alb 0
#define gri 1
#define negru 2
#define MAX 100001
vector <int> vecin[MAX];
long v_culoare[MAX];
long unsigned n , m, nr = 0;
void citire()
{
long unsigned i, x, y;
freopen( "dfs.in", "r", stdin);
scanf("%lu%lu ", &n , &m);
for(i = m; i > 0; i--)
{
scanf("%lu%lu", &x ,&y);
vecin[x].push_back(y);
vecin[y].push_back(x);
}
}
void df(int nod)
{
v_culoare[nod] = gri;
vector<int>::iterator it;
for(it = vecin[nod].begin(); it != vecin[nod].end(); ++it)
if(v_culoare[*it] == alb )
df(*it);
v_culoare[nod] = negru;
}
void componente_conexe()
{
int i;
for(i = n; i > 0; i--)
if(v_culoare[i] == alb)
{
nr++;
df(i);
}
}
int main()
{
citire();
componente_conexe();
freopen("dfs.out", "w", stdout);
printf("%lu", nr);
return 0;
}