Pagini recente » Cod sursa (job #3321747) | Cod sursa (job #3304347) | Cod sursa (job #3314517) | Cod sursa (job #3320595) | Cod sursa (job #469679)
Cod sursa(job #469679)
#include <fstream.h>
#include <queue>
using namespace std;
#define nmax (100005)
int N, M, A;
int *G[nmax];
bool Viz[nmax];
queue<int> Q;
// read data
void read() {
// read graph size
ifstream fin("dfs.in");
fin >> N >> M;
// prepare lists
for (int i = 1; i <= N; ++i) {
G[i] = (int*) malloc(sizeof (int));
G[i][0] = 0;
}
// read degrees
while (M--) {
int x, y;
fin >> x >> y;
G[x][0]++;
G[y][0]++;
}
fin.close();
// prepare lists for incoming degrees
for (int i = 1; i <= N; ++i) {
G[i] = (int*) realloc(G[i], (G[i][0] + 1) * sizeof (int));
G[i][0] = 0;
}
// read actual vertices
ifstream fim("dfs.in");
fim >> N >> M;
while (M--) {
int x, y;
fim >> x >> y;
G[x][++G[x][0]] = y;
G[y][++G[y][0]] = x;
}
fim.close();
}
// solve task
void solve() {
for (int k = 1; k <= N; ++k) {
if (!Viz[k]) {
++A;
Viz[k] = 1;
for (Q.push(k); !Q.empty(); Q.pop()) {
int v = Q.front();
for (int i = 1; i <= G[v][0]; ++i) {
int w = G[v][i];
if (!Viz[w]) {
Viz[w] = 1;
Q.push(w);
}
}
}
}
}
}
// write data
void write() {
// write array
ofstream fout("dfs.out");
fout << A << '\n';
fout.close();
}
int main() {
read();
solve();
write();
return 0;
}