Pagini recente » Cod sursa (job #1949745) | Cod sursa (job #1481690) | Cod sursa (job #1526258) | Cod sursa (job #2536567) | Cod sursa (job #1087696)
#include <fstream>
#include <cstring>
#include <cstdlib>
using namespace std;
const int N = 1 + 1e5, nil = 0xffffffff;
class Graph{
int *begin, *buff, *nxt;
int pos;
public:
void init(int n, int m){
n++;
begin = (int*)malloc(n * sizeof(int));
memset(begin, nil, n * sizeof(int));
buff = (int*)malloc(m * sizeof(int));
nxt = (int*)malloc(m * sizeof(int));
memset(nxt, nil, m * sizeof(int));
pos = 0;
}
void insert(int x, int y){
buff[pos] = y;
nxt[pos] = begin[x];
begin[x] = pos;
pos++;
}
inline int operator[](int x){
return buff[x];
}
inline int start(int x){
return begin[x];
}
inline int next(int x){
return nxt[x];
}
inline int stop(int x){
return nil;
}
};
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 = G.next(it))
if (!use[ G[it] ])
dfs( G[it] );
}
int main(){
int n, m, x, y, ans = 0;
in >> n >> m;
G.init(n, 2 * m);
while (m--){
in >> x >> y;
G.insert(x, y);
G.insert(y, x);
}
for (int i = 1 ; i <= n ; i++)
if (!use[i]){
dfs(i);
ans++;
}
out << ans << "\n";
return 0;
}