Examples
Example 1
Input
3 4
0 1
1 2
2 3
Output
0
1
2
3
Explanation
Since all the planets are connected with one path and cannot be accessed by any alternative paths hence all the planets are critical.
Example 2
Input
7 6
0 2
0 1
1 2
2 3
4 5
3 4
3 5
Output
2
3
Explanation
If the republic loose the path between 2 and 3 then the two system of planets will not be able to communicate with each other. Hence 2 and 3 are critical planets.
Solution
As per the problem statement we need to create a graph using the given number of edges and vertices and find the critical node from it.
Critical nodes are a group of nodes whose removal causes the network to fracture the most.
Implementation in C++
The following code illustrates the solution in C++ :
#include <bits/stdc++.h>
typedef long long int lli;
#define pb push_back
using namespace std;
vector<int> adj[100001];
int visited[100001] , in[100001] ,low[100001];
int timer;
set<int> s;
void dfs(int node , int pre)
{
visited[node] = 1;
in[node] = low[node] = timer;
timer++;
for(int i : adj[node])
{
if(i == pre)
continue;
if(visited[i] == 1)
{
low[node] = min(low[node] , in[i]);
}
else
{
dfs(i , node);
if(low[i] > in[node])
s.insert(node) , s.insert(i);
low[node] = min(low[node] , low[i]);
}
}
}
int main()
{
int edge, vertex , a , b;
cin >> edge >> vertex;
for(int i = 0;i < edge;i++)
{
cin >> a >> b;
adj[a].pb(b);
adj[b].pb(a);
}
dfs(0 , -1);
for(int i : s)
cout << i << endl;
return 0;
}
You can also try this code with Online C++ Compiler
Implementation in Java
The following code illustrates the solution in Java :
import java.util.*;
public class Main {
static List<List<Integer>> graph;
static TreeSet<Integer> criticalPlanets;
static boolean[] visited;
static int[] inTime;
static int[] low;
static int timer = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
graph = new ArrayList<>(n);
for (int i = 0; i < n; i++)
graph.add(new ArrayList<>());
visited = new boolean[n];
inTime = new int[n];
low = new int[n];
criticalPlanets = new TreeSet<>();
for (int i = 0; i < m; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
graph.get(u).add(v);
graph.get(v).add(u);
}
dfs(0, -1);
for (int i : criticalPlanets)
System.out.println(i);
}
public static void dfs(int node, int parent) {
visited[node] = true;
inTime[node] = low[node] = timer++;
for (int neighbour : graph.get(node)) {
if (neighbour == parent)
continue;
if (visited[neighbour])
low[node] = Math.min(low[node], inTime[neighbour]);
else {
dfs(neighbour, node);
if (low[neighbour] > inTime[node]) {
criticalPlanets.add(neighbour);
criticalPlanets.add(node);
}
low[node] = Math.min(low[node], low[neighbour]);
}
}
}
}
You can also try this code with Online Java Compiler
Implementation in Python
The following code illustrates the solution in Python :
timer=0
def dfs (cur, par, timer):
vis[cur]=1
if cur!=0:
low[cur] = trav[cur] = trav[par] + 1
timer += 1
for i in g[cur]:
if i == par:
continue
if vis[i]==1:
low[cur] = min ( low[cur], trav[i] )
else:
dfs(i, cur, timer)
if low[i]>low[cur]:
defend.add(i)
defend.add(cur)
low[cur] = min (low[cur], low[i])
e, n = map(int, input().split())
g = []
vis = []
low = []
trav = []
for i in range(n):
l = []
vis.append(0)
low.append(0)
trav.append(0)
g.append(l)
for i in range(e):
a, b = map(int, input().split())
g[a].append(b)
g[b].append(a)
defend = set()
dfs(0, -1, timer)
defend = list(defend)
defend.sort()
for i in defend:
print(i)
You can also try this code with Online Python Compiler
Check out this article to find out everything about TCS NQT.
FAQs
-
What is TCS Codevita?
The Pre-Qualifier Round, the Qualifier Round, and the Grand Finale are the three major rounds of CodeVita, an online coding competition. 1. Pre-Qualifier Round: This will be an online coding competition in which players will have 6 hours to complete questions.
-
What are the requirements for TCS CodeVita participation?
The CodeVita competition is open to students from India's institutes who will finish their academic degrees in 2022, 2023, 2024, or 2025.
-
What languages will we be able to code in the exam?
The languages that we can use are as follows: C, C++, C#, Java, Perl, PHP, Python, and Ruby.
Key Takeaways
In this article, we have extensively discussed the problem Critical Planets asked in TCs Codevita 2021.The article explains the details of the problem statement along with the problem statement and its implementation in various programming languages like C++, Java, and Python.
We hope that this blog has helped you enhance your knowledge regarding Critical Planets problem asked in TCS Codevita2021 and if you would like to learn more, visit Coding Ninjas Studio, our practice platform, to practise top problems, take mock tests, read interview experiences, and much more technical stuff.
You can also consider our Competitive Programming Course to give your career an edge over others. Do upvote our blog to help other ninjas grow.
Happy Coding!
34+ registered 
