Pagini recente » Cod sursa (job #2793100) | Cod sursa (job #267686) | Cod sursa (job #394271) | Cod sursa (job #1345474) | Cod sursa (job #1556748)
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int dmax = 100000;
const int dim = 1000000;
struct MUCHIE {int a, b;};
MUCHIE m[2*dim + 1];
int inc[dmax+1];
int k;
int viz[dmax+1];
int N,M, NR;
void DFS(int x)
{
viz[x] = true;
//printf("%d ", x);
//PARCURG LISTA VECINILOR LUI X
for(int i = inc[x]; m[i].a == x; i++)
if(viz[ m[i].b ] == false) DFS(m[i].b);
}
bool exc(MUCHIE e1, MUCHIE e2)
{
if(e1.a == e2.a) return e1.b < e2.b;
else
return e1.a < e2.a;
}
int main()
{
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
int i, x, y;
scanf("%d %d", &N, &M);
for(i = 1; i <= M; i++)
{
scanf("%d %d", &x, &y);
k++;
m[k].a = x;
m[k].b = y;
k++;
m[k].a = y;
m[k].b = x;
}
sort(m+1, m+k+1, exc);
/*for(i = 1; i <= k; i++) printf("%d ", m[i].a);
printf("\n");
for(i = 1; i <= k; i++) printf("%d ", m[i].b);
printf("\n");*/
inc[1] = 1;
for(i = 2; i <= k; i++)
if(m[i].a != m[i-1].a)
inc[ m[i].a ] = i;
//for(i = 1; i <= N; i++) printf("%d ", inc[i]);
//printf("\n");
for(i = 1; i <= N; i++)
if(viz[i] == false)
{
NR++;
DFS(i);
//printf("\n");
}
printf("%d", NR);
return 0;
}