CPP Program Bottom Problem – Advanced Graphs

  • We will use the following (standard) definitions from graph theory. Let V be a non-empty and finite set, its elements being called vertices (or nodes). Let E be a subset of the Cartesian product V×V, its elements being called edges. Then G=(V,E) is called a directed graph.
  • Let n be a positive integer, and let p=(e1,…,en) be a sequence of length n of edges ei∈E such that ei=(vi,vi+1)for a sequence of vertices (v1,…,vn+1). Then p is called a path from vertex v1 to vertex vn+1 in G and we say that vn+1 is reachable from v1, writing (v1→vn+1).
  • Here are some new definitions. A node v in a graph G=(V,E) is called a sink, if for every node w in G that is reachable from v, v is also reachable from w. The bottom of a graph is the subset of all nodes that are sinking, i.e., bottom(G)={v∈V∣∀w∈V:(v→w)⇒(w→v)}. You have to calculate the bottom of certain graphs.

Input Specification

  • The input contains several test cases, each of which corresponds to a directed graph G. Each test case starts with an integer number v, denoting the number of vertices of G=(V,E) where the vertices will be identified by the integer numbers in the set V={1,…,v}. You may assume that 1≤v≤5000. That is followed by a non-negative integer e and, thereafter, e pairs of vertex identifiers v1,w1,…, ve, we with the meaning that (vi, wi)∈E. There are no edges other than those specified by these pairs. The last test case is followed by a zero.

Output Specification

  • For each test case output the bottom of the specified graph on a single line. To this end, print the numbers of all nodes that sink in sorted order separated by a single space character. If the bottom is empty, print an empty line.

Sample Input:

3 3
1 3 2 3 3 1
2 1
1 2
0

Sample Output:

1 3 2

Code:

#include <iostream> #include <vector> #include <unordered_set> #include <stack> #include<algorithm> #include <iterator> using namespace std; void dfs(vector<int> *edges, int start, unordered_set<int> &visited, stack<int> &finished_vertices_stack) { visited.insert(start); for (int i = 0; i < edges[start].size(); i++) { int adjacent = edges[start][i]; if (visited.count(adjacent) == 0) { dfs(edges, adjacent, visited, finished_vertices_stack); } } finished_vertices_stack.push(start); } void dfs2(vector<int> *edgesT, int start, unordered_set<int> &visited, unordered_set<int> *component) { visited.insert(start); component->insert(start); for (int i = 0; i < edgesT[start].size(); i++) { int adjacent = edgesT[start][i]; if (visited.count(adjacent) == 0) { dfs2(edgesT, adjacent, visited, component); } } } unordered_set<unordered_set<int> *> *getSCC(vector<int> *edges, vector<int> *edgesT, int n) { unordered_set<int> visited; stack<int> finished_vertices_stack; for (int i = 0; i < n; i++) { if (visited.count(i) == 0) { dfs(edges, i, visited, finished_vertices_stack); } } visited.clear(); unordered_set<unordered_set<int> *> *output = new unordered_set<unordered_set<int> *>(); while (!finished_vertices_stack.empty()) { int element = finished_vertices_stack.top(); finished_vertices_stack.pop(); if (visited.count(element) == 0) { unordered_set<int> *component = new unordered_set<int>(); dfs2(edgesT, element, visited, component); output->insert(component); } } return output; } int main() { while (true) { int v; //vertices cin >> v; if (v == 0) { return 0; } int e; cin >> e; vector<int> *edges = new vector<int>[v]; vector<int> *edgesT = new vector<int>[v]; for (int i = 0; i < e; i++) { int j, k; cin >> j >> k; edges[j - 1].push_back(k - 1); edgesT[k - 1].push_back(j - 1); } unordered_set<unordered_set<int> *> *components = getSCC(edges, edgesT, v); auto it = components->begin(); vector<int> ans; while (it != components->end()) { int flag = 0; auto it2 = (*it)->begin(); while (it2 != (*it)->end()) { for (int i = 0; i < edges[*it2].size(); ++i) { if ((*it)->count(edges[*it2].at(i)) == 0) { flag = 1; break; } } if (flag == 1) { break; } it2++; } if (flag == 0) { it2 = (*it)->begin(); while (it2 != (*it)->end()) { ans.push_back(*it2 + 1); it2++; } } it++; } sort(ans.begin(), ans.end()); for (int i = 0; i < ans.size(); ++i) { cout << ans.at(i) << " "; } cout<<endl; } }
Code language: C++ (cpp)

Leave a Comment