Cod sursa(job #2745174)

Utilizator matthriscuMatt . matthriscu Data 25 aprilie 2021 22:55:03
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#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;
}