DFS in C++

README.md

Depth-first search

Finding number of strongly connected components in graph.

example.in

12
1 3
0
2 0 1
1 2
3 2 5 8
4 2 3 6 10
2 3 7
1 11
1 10
1 4
2 9 11
1 6

example.out

4

example.png

main.cpp

#include <iostream>
#include <vector>
#include <algorithm>

enum NodeState { FRESH, OPEN, CLOSED };

class Node {
    public:
        int index;
        int opened;
        int closed;
        int followers;
        NodeState state;
        Node *parent;
        std::vector<int> following;

        Node (int index) {
            this->index = index;
            this->opened = -1;
            this->closed = -1;
            this->state = FRESH;
            this->parent = NULL;
            this->followers = 0;
        }

        void open (int val, Node *parent = NULL) {
            this->opened = val;
            this->state = OPEN;
            this->parent = parent;
        }

        void close (int val) {
            this->closed = val;
            this->state = CLOSED;
        }

        void push (int val) {
            this->followers++;
            (this->following).push_back(val);
        }
};

void dfsAction (std::vector<Node*> graph, int &iteration, Node * curr) {
    curr->open(iteration++);
    for (int i=0; i<curr->followers; i++) {
        int id = curr->following[i];
        if (graph[id]->state==FRESH) {
            graph[id]->parent = curr;
            dfsAction(graph,iteration,graph[id]);
        }
    }
    curr->close(iteration++);
}

void buildGraph (std::vector<Node*>& graph) {
    int num, tmp1,tmp2;
    std::cin >> num;
    for (int i=0; i<num; i++) {
        std::cin >> tmp1;
        graph.push_back(new Node(i));
        for (int j=0; j<tmp1; j++) {
            std::cin >> tmp2;
            (graph.back())->push(tmp2);
        }
    }
}

bool sorting(Node *i, Node *j) {
    return (i->closed>j->closed);
}

void buildReversed (std::vector<Node*>& original, std::vector<Node*>& reversed, std::vector<int>& order) {
    for (unsigned int i=0; i<original.size(); i++) {
        reversed.push_back(new Node(i));
    }

    for (unsigned int i=0; i<original.size(); i++) {
        for (int j=0; j<original[i]->followers; j++) {
            reversed[original[i]->following[j]]->push(i);
        }
    }

    std::sort (original.begin(), original.end(), sorting);

    for (unsigned int i=0; i<original.size(); i++) {
        order.push_back(original[i]->index);
    }
}

int main (int argc, char **argv) {
    int iteration, components;
    std::vector<Node*> graph;
    std::vector<Node*> reversed;
    std::vector<int> order;

    buildGraph(graph);
    iteration = 0;
    for (unsigned int i=0; i<graph.size(); i++) {
        if (graph[i]->state==FRESH) {
            dfsAction(graph,iteration,graph[i]);
        }
    }

    buildReversed(graph, reversed, order);
    iteration = 0;
    components = 0;
    for (unsigned int i=0; i<order.size(); i++) {
        if (reversed[order[i]]->state==FRESH) {
            dfsAction(reversed,iteration,reversed[order[i]]);
            components++;
        }
    }

    std::cout << components << std::endl;

    return 0;
}