Pagini recente » Cod sursa (job #2974216) | Cod sursa (job #2067094) | Cod sursa (job #85298) | Cod sursa (job #2139134) | Cod sursa (job #1315736)
#include <cstring>
#define NMAX 100001
struct node {
int key;
node *next;
node() {
next = NULL;
}
};
class List {
private:
node *first, *last;
public:
List() {
first = last = NULL;
}
node *front() {
return first;
}
void push_back(int key) {
node *p;
p = new node;
p->key = key;
if (last != NULL) last->next = p;
else first = p;
last = p;
}
};
class stack {
private:
node *first;
public:
stack() {
first = NULL;
}
int top() {
if (first != NULL) return first->key;
}
bool empty() {
if (first == NULL) return 1;
return 0;
}
void pop() {
node *p = first;
first = first->next;
delete p;
}
void push(int x) {
node *p;
p = new node;
p->key = x;
p->next = first;
first = p;
}
};
class Graph {
private:
int N, components, comp[NMAX];
List v[NMAX];
bool visited[NMAX];
void visit(int node) {
comp[node] = components;
}
public:
Graph() {
memset(v, NULL, sizeof(v));
memset(comp, 0, sizeof(comp));
memset(comp, 0, sizeof(visited));
}
void setSize(int n) {
N = n;
}
void addEdge(int i, int j) {
v[i].push_back(j);
}
void DFS(int Node) {
node *p;
p = v[Node].front();
visit(Node);
visited[Node] = 1;
while (p != NULL) {
if (!visited[p->key])
DFS(p->key);
p = p->next;
}
}
int getComponents() {
components = 0;
for (int i = 1; i <= N; i++) {
if (!visited[i]) {
components++;
DFS(i);
}
}
return components;
}
} G;
#include <fstream>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int main()
{
int N, M;
f >> N >> M;
G.setSize(N);
int x, y;
while (M--) {
f >> x >> y;
G.addEdge(x, y);
G.addEdge(y, x);
}
g << G.getComponents();
return 0;
}