## BOTTOM - The Bottom of a Graph

no tags

We will use the following (standard) definitions from graph theory. Let V be a nonempty 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)�=(�1,…,��) be a sequence of length n of edges eiE��∈� such that ei=(vi,vi+1)��=(��,��+1) for a sequence of vertices (v1,,vn+1�1,…,��+1). Then p is called a path from vertex v1�1 to vertex vn+1��+1 in G and we say that vn+1��+1 is reachable from v1�1, writing (v1vn+1)(�1→��+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 vv is also reachable from w. The bottom of a graph is the subset of all nodes that are sinks, i.e., bottom(G)={vVwV:(vw)(wv)}bottom(�)={�∈�∣∀�∈�:(�→�)⇒(�→�)}. 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}�={1,…,�}. You may assume that 1v50001≤�≤5000. That is followed by a non-negative integer e and, thereafter, e pairs of vertex identifiers v1,w1,,ve,we�1,�1,…,��,�� with the meaning that (vi,wi)E(��,��)∈�. There are no edges other than 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 are sinks in sorted order separated by a single space character. If the bottom is empty, print an empty line.

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

1 3
2

## Code Examples

### #1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>
#include <limits.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

#define MOD (ll)1000000007
#define pb   push_back
#define EPS 1e-9
#define FOR(i,n)  for(int i = 0;i < n; i++)
#define FORE(i,a,b) for(int i = a;i <= b; i++)
#define pi(a)   printf("%d\n", a)
#define all(c)  c.begin(), c.end()
#define tr(container, it)   for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define gc getchar_unlocked
#define sdi(a, b)   si(a);si(b)
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define endl '\n'
#define F first
#define S second
#define FILL(arr, val)  memset(arr, val, sizeof(arr))
#define read(arr, n)    for(int i = 0;i < n; i++)cin>>arr[i];
#define sp ' '

template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}

void si(int &x){
register int c = gc();
x = 0;
int neg = 0;
for(;((c<48 || c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg> x=-x;
}

const int MAXN = 5e3+5;
int components[MAXN];   //components[i] indicates to which component i belongs to.
int out_degree[MAXN];
int n;
bool vis[MAXN];
stack<int> stk;
int numberOfComponents;

void initialize(){
}

void dfs(int src){
vis[src] = 1;
}
}
//ordering the vertices according to the finish times, the vertex finishing last will be at the top of stack.
stk.push(src);
}

void dfsF(int src){
vis[src] = 1;
components[src] = numberOfComponents;
}
}
}

void scc(){
while(!stk.empty()){
int ele = stk.top();
stk.pop();
if(!vis[ele]){
numberOfComponents++;
dfsF(ele);
}
}
}

int main(){
io;
while(1){
cin >> n;
if(n == 0)
break;
initialize();
int m;
cin >> m;
FOR(i,m){
int a, b;
cin >> a >> b;
}
for(int i = 1;i <= n; i++){
if(!vis[i]){
dfs(i);
}
}
FORE(i,1,n) vis[i] = false;
scc();
//DAG of SCC is formed calculate indegree of components
for(int i = 1;i <= n; i++){
for(int j = 0;j < adj[i].size(); j++){
out_degree[components[i]]++;
}
}
}
int countZeroOutDegree = 0;
FORE(i,1,numberOfComponents){
if(out_degree[i] == 0){
countZeroOutDegree++;
}
}
if(countZeroOutDegree == 0){
cout << endl;
}else{
FORE(i,1,n){
if(out_degree[components[i]] == 0){
cout << i << sp;
}
}
cout << endl;
}
}
return 0;
}
Copy The Code &

Input

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

Output

cmd
1 3
2