Pagini recente » Cod sursa (job #597645) | Cod sursa (job #1477948) | Cod sursa (job #650087) | Cod sursa (job #1856876) | Cod sursa (job #2818314)
#include <fstream>
using namespace std;
struct Node{
int value;
Node* next;
};
void explore(Node* adj_list[], int x, bool visited[]){
visited[x] = true;
Node* temp = adj_list[x];
while(temp != NULL){
if(!visited[temp -> value]){
explore(adj_list, temp -> value, visited);
}
temp = temp -> next;
}
}
int DFS(Node* adj_list[], int N){
bool visited[N] = {false};
int cnt = 0;
for(int i = 0; i < N; ++i){
if(!visited[i]){
cnt++;
explore(adj_list, i, visited);
}
}
return cnt;
}
void add(Node* &dest, int value){
Node* p = new Node;
p -> value = value;
p -> next = dest;
dest = p;
}
int main(){
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int N, M;
fin >> N >> M;
Node* adj_list[N] = {NULL};
for(int i = 0; i < M; ++i){
int x, y;
fin >> x >> y;
add(adj_list[x - 1], y - 1);
add(adj_list[y - 1], x - 1);
}
int cnt = DFS(adj_list, N);
fout << cnt << "\n";
return 0;
}