Number of sink nodes in a graph
Last Updated :
20 Feb, 2023
Given a Directed Acyclic Graph of n nodes (numbered from 1 to n) and m edges. The task is to find the number of sink nodes. A sink node is a node such that no edge emerges out of it.
Examples:
Input : n = 4, m = 2
Edges[] = {{2, 3}, {4, 3}}
Output : 2
Only node 1 and node 3 are sink nodes.
Input : n = 4, m = 2
Edges[] = {{3, 2}, {3, 4}}
Output : 3
The idea is to iterate through all the edges. And for each edge, mark the source node from which the edge emerged out. Now, for each node check if it is marked or not. And count the unmarked nodes.
Algorithm:
1. Make any array A[] of size equal to the
number of nodes and initialize to 1.
2. Traverse all the edges one by one, say,
u -> v.
(i) Mark A[u] as 1.
3. Now traverse whole array A[] and count
number of unmarked nodes.
Below is implementation of this approach:
C++
#include<bits/stdc++.h>
using namespace std;
int countSink(int n, int m, int edgeFrom[],
int edgeTo[])
{
int mark[n];
memset(mark, 0, sizeof mark);
for (int i = 0; i < m; i++)
mark[edgeFrom[i]] = 1;
int count = 0;
for (int i = 1; i <= n ; i++)
if (!mark[i])
count++;
return count;
}
int main()
{
int n = 4, m = 2;
int edgeFrom[] = { 2, 4 };
int edgeTo[] = { 3, 3 };
cout << countSink(n, m, edgeFrom, edgeTo) << endl;
return 0;
}
|
Java
import java.util.*;
class GFG
{
static int countSink(int n, int m,
int edgeFrom[], int edgeTo[])
{
int []mark = new int[n + 1];
for (int i = 0; i < m; i++)
mark[edgeFrom[i]] = 1;
int count = 0;
for (int i = 1; i <= n ; i++)
if (mark[i] == 0)
count++;
return count;
}
public static void main(String[] args)
{
int n = 4, m = 2;
int edgeFrom[] = { 2, 4 };
int edgeTo[] = { 3, 3 };
System.out.println(countSink(n, m,
edgeFrom, edgeTo));
}
}
|
Python3
def countSink(n, m, edgeFrom, edgeTo):
mark = [0] * (n + 1)
for i in range(m):
mark[edgeFrom[i]] = 1
count = 0
for i in range(1, n + 1):
if (not mark[i]):
count += 1
return count
if __name__ == '__main__':
n = 4
m = 2
edgeFrom = [2, 4]
edgeTo = [3, 3]
print(countSink(n, m, edgeFrom, edgeTo))
|
C#
using System;
class GFG
{
static int countSink(int n, int m,
int []edgeFrom,
int []edgeTo)
{
int []mark = new int[n + 1];
for (int i = 0; i < m; i++)
mark[edgeFrom[i]] = 1;
int count = 0;
for (int i = 1; i <= n ; i++)
if (mark[i] == 0)
count++;
return count;
}
public static void Main(String[] args)
{
int n = 4, m = 2;
int []edgeFrom = { 2, 4 };
int []edgeTo = { 3, 3 };
Console.WriteLine(countSink(n, m,
edgeFrom, edgeTo));
}
}
|
Javascript
<script>
function countSink(n, m, edgeFrom, edgeTo)
{
let mark = new Array(n + 1);
for(let i = 0; i < n + 1; i++)
{
mark[i] = 0;
}
for(let i = 0; i < m; i++)
mark[edgeFrom[i]] = 1;
let count = 0;
for(let i = 1; i <= n; i++)
if (mark[i] == 0)
count++;
return count;
}
let n = 4, m = 2;
let edgeFrom = [ 2, 4 ];
let edgeTo = [ 3, 3 ];
document.write(countSink(n, m,
edgeFrom, edgeTo));
</script>
|
Output:
2
Time Complexity: O(m + n) where n is number of nodes and m is number of edges.
Space complexity : O(n) because it uses an array of size n to store the non-sink nodes.
Related Article:
The Celebrity Problem
Please Login to comment...