# 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:

```.wp-block-code {
border: 0;
}

.wp-block-code > span {
display: block;
overflow: auto;
}

.shcb-language {
border: 0;
clip: rect(1px, 1px, 1px, 1px);
-webkit-clip-path: inset(50%);
clip-path: inset(50%);
height: 1px;
margin: -1px;
overflow: hidden;
position: absolute;
width: 1px;
word-wrap: normal;
word-break: normal;
}

.hljs {
box-sizing: border-box;
}

.hljs.shcb-code-table {
display: table;
width: 100%;
}

.hljs.shcb-code-table > .shcb-loc {
color: inherit;
display: table-row;
width: 100%;
}

.hljs.shcb-code-table .shcb-loc > span {
display: table-cell;
}

.wp-block-code code.hljs:not(.shcb-wrap-lines) {
white-space: pre;
}

.wp-block-code code.hljs.shcb-wrap-lines {
white-space: pre-wrap;
}

.hljs.shcb-line-numbers {
border-spacing: 0;
counter-reset: line;
}

.hljs.shcb-line-numbers > .shcb-loc {
counter-increment: line;
}

.hljs.shcb-line-numbers .shcb-loc > span {
}

.hljs.shcb-line-numbers .shcb-loc::before {
border-right: 1px solid #ddd;
content: counter(line);
display: table-cell;
text-align: right;
-webkit-user-select: none;
-moz-user-select: none;
-ms-user-select: none;
user-select: none;
white-space: nowrap;
width: 1%;
}
```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)```