Pagini recente » Cod sursa (job #261143) | Cod sursa (job #3170690) | Cod sursa (job #1295693) | Cod sursa (job #1617680) | Cod sursa (job #1087693)
#include <fstream>
#include <cstring>
#include <cstdlib>
using namespace std;
const int N = 1 + 1e8;
class Graph{ ///WORKS WITH |V| < 2 ^ 21
long long* buff;
int *vect, *grad;
int nrV, pos, posM;
bool UnOriented;
void addInt(long long x){
buff[pos] ^= x << posM;
if (posM == 42){
posM = 0;
pos++;
} else
posM += 21;
}
int getInt(){
if (posM == 0){
posM = 42;
pos--;
} else
posM -= 21;
return ( buff[pos] >> posM ) & ((1 << 21) - 1);
}
public:
void init(int n, int m, bool UnOr){
UnOriented = UnOr;
nrV = n;
n += 2;
m = 1 + 2 * m / 3;
buff = (long long*)malloc( m * sizeof(long long) );
memset(buff, 0, m * sizeof(long long));
grad = (int*)malloc(n * sizeof(int));
memset(grad, 0, n * sizeof(int));
pos = posM = 0;
}
void insert(int x, int y){
addInt(x); addInt(y);
grad[x]++;
if (UnOriented) grad[y]++;
}
void build(){
for (int i = 1 ; i <= nrV + 1 ; i++)
grad[i] += grad[i - 1];
vect = (int*) malloc( grad[nrV + 1] * sizeof(int) );
if (UnOriented){
int x, y;
while (pos || posM){
y = getInt();
x = getInt();
vect[ --grad[x] ] = y;
vect[ --grad[y] ] = x;
}
} else
while (pos || posM)
vect[ grad[ getInt() ]++ ] = getInt();
free(buff);
}
inline int* start(int x){
return vect + grad[x];
}
inline int* stop(int x){
return vect + grad[x + 1];
}
};
Graph G;
bool use[N];
ifstream in("dfs.in");
ofstream out("dfs.out");
void dfs(int x){
use[x] = true;
for (int* it = G.start(x) ; it != G.stop(x) ; it++)
if (!use[*it])
dfs(*it);
}
int main(){
int n, m, x, y, ans = 0;
in >> n >> m;
G.init(1e6, 1e7, 1);
while (m--){
in >> x >> y;
G.insert(x, y);
}
G.build();
for (int i = 1 ; i <= n ; i++)
if (!use[i]){
dfs(i);
ans++;
}
out << ans << "\n";
return 0;
}