Pagini recente » Cod sursa (job #2296370) | Cod sursa (job #1934884) | Cod sursa (job #2134674) | Cod sursa (job #2848681) | Cod sursa (job #1087665)
#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;
posM += 21;
if (posM == 63){
posM = 0;
pos++;
}
}
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;
buff = (long long*)malloc( (1 + 2 * m / 3) * sizeof(long long) );
memset(buff, 0, (1 + 2 * m / 3) * sizeof(long long));
if (UnOriented) m <<= 1;
vect = (int*)malloc(m * sizeof(int));
grad = (int*)malloc((n + 2) * sizeof(int));
memset(grad, 0, (n + 2) * 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];
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(n, m, 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;
}