Pagini recente » Cod sursa (job #792260) | Cod sursa (job #2324749) | Cod sursa (job #1820890) | Cod sursa (job #1243857) | Cod sursa (job #805428)
Cod sursa(job #805428)
#include <cstdio>
class ListNode {
private:
int data;
public:
ListNode *next;
ListNode(int x) {
data = x;
}
ListNode(int x, ListNode *next) {
data = x;
this->next = next;
}
int get() {
return data;
}
bool hasNext() {
return next != NULL;
}
};
class List {
private:
ListNode *head;
bool marked;
public:
List() {
head = NULL;
marked = false;
}
void add(int x) {
ListNode *new_node = new ListNode(x, head);
head = new_node;
}
ListNode* operator[](int index) {
ListNode *p = head;
for(int i = 1; i <= index; ++i) {
if(p == NULL)
break;
p = p->next;
}
return p;
}
void mark() {
marked = true;
}
bool isMarked() {
return marked;
}
~List() {
ListNode *p = head;
ListNode *q;
while(p != NULL) {
q = p;
p = p->next;
delete q;
}
}
};
List *v;
void dfs(int node) {
v[node].mark();
ListNode *p = v[node][0];
for(; p != NULL; p = p->next) {
if(!v[p->get()].isMarked())
dfs(p->get());
}
}
int main() {
int n, m;
FILE* in = fopen("dfs.in", "r");
FILE* out = fopen("dfs.out", "w");
fscanf(in, "%d%d", &n, &m);
int x, y;
v = new List[n + 1];
for(int i = 1; i <= n; ++i) {
fscanf(in, "%d%d", &x, &y);
v[x].add(y);
v[y].add(x);
}
int compcon = 0;
for(int i = 1; i <= n; ++i) {
if(!v[i].isMarked()) {
compcon++;
dfs(i);
}
}
fprintf(out, "%d", compcon);
return 0;
}