Pagini recente » Cod sursa (job #2825733) | Cod sursa (job #698112) | Cod sursa (job #1623002) | Diferente pentru problema/dijkstra intre reviziile 28 si 27 | Cod sursa (job #2745174)
#include <fstream>
using namespace std;
#define NMAX 100005
struct Node {
int info;
Node* next = NULL;
Node(int x) {
info = x;
}
Node() {}
};
struct List {
Node *head = NULL, *end = NULL;
void add(int x) {
if(head == NULL) {
head = new Node(x);
end = head;
}
else {
end -> next = new Node(x);
end = end -> next;
}
}
};
struct Stack {
Node *head = NULL;
int size = 0;
void push(int x) {
++size;
if(head == NULL)
head = new Node(x);
else {
Node *temp = head;
head = new Node(x);
head -> next = temp;
}
}
int pop() {
if(size == 0)
return -1;
--size;
Node *temp = head;
int r = head -> info;
if(head -> next != NULL)
head = head -> next;
delete temp;
return r;
}
};
List G[NMAX];
bool vis[NMAX];
void dfs(int node) {
Stack st;
Node *temp;
int current;
st.push(node);
while(st.size) {
current = st.pop();
vis[current] = 1;
temp = G[current].head;
while(temp != NULL) {
if(vis[temp -> info] == 0)
st.push(temp -> info);
temp = temp -> next;
}
}
}
int main() {
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n, m, i, x, y, ans = 0;
fin >> n >> m;
for(i = 1; i <= m; ++i) {
fin >> x >> y;
G[x].add(y);
G[y].add(x);
}
for(i = 1; i <= n; ++i)
if(!vis[i]) {
++ans;
dfs(i);
}
fout << ans;
}