Editorial for Действия


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.
by: doncho
class Graph {
    constructor(verticesCount) {
        this.nodes = [];
        this.sources = new Set();

        for (let i = 0; i < verticesCount; i += 1) {
            this.nodes.push({
                parents: 0,
                children: [],
            });

            // mark all vertices as potential sources
            this.sources.add(i);
        }
    }

    addEdge(from, to) {
        this.nodes[from].children.push(to);
        this.nodes[to].parents += 1;

        // to has an incoming edge, so it cannot be source...
        this.sources.delete(to);
    }

    getSorted() {
        // Save the result
        const path = [];

        while (this.sources.size > 0) {
            // Get the minimal source, by order 0, 1, 2, 3, 4, 5, 6, ....
            const source = Math.min(...this.sources);

            // Remove it from sources
            this.sources.delete(source);
            path.push(source);

            // Remove all edges outgoing of **source**
            for (const child of this.nodes[source].children) {
                // Update the prant
                this.nodes[child].parents -= 1;

                // **child** is a source (there are no incoming edges)
                if (this.nodes[child].parents === 0) {
                    this.sources.add(child);
                }
            }
        }

        return path;
    }
}

Comments

There are no comments at the moment.