PROBLEM LINK:
Author: sumit
Tester: Neeraj
Editorialist: Manish
DIFFICULTY:
EASY.
PREREQUISITES:
Math , Graph.
PROBLEM:
We all love the avengers and we all hate thanos. We know the main mission of thanos is to wipe out half of the population of the planet. But there are alternate universes, and in these universes too Thanos is the evil and the avengers are the heroes. But now we will not talk about avengers , in fact you need to help Thanos. In these universes Thanos not like to just wipe out half of the population, but he wants to destroy planets. In these universes, there is a special system/layout of the planets that the planets are interdependent on each other i.e. if one planet gets destroyed, the next one also gets destroyed and so…on. However, sometimes destruction of one planet fails to destroy the next one. In that case Thanos himself need to destroy the planets to start the chain again. And thanos wants to destroy all the planets and you need to help him.
So, your task is to determine , given the system/layout of some planets, the minimum number of planets Thanos needs to destroy himself such that all the planets gets destroyed.
SOLUTIONS:
Setter's Solution
Tester's Solution
Manish'sSolution
#include<bits/stdc++.h>
using namespace std;
#define endl “\n”
#define pb push_back
#define ll long long
#define fio ios_base::sync_with_stdio(0); cin.tie(NULL);
#define N (int)(1e5+1)
vector ordering;
bool used[N];
void dfs1(vector g[], int u)
{
used[u] = true;
for(int i=0; i<g[u].size(); i++)
{
if(!used[g[u][i]])
dfs1(g,g[u][i]);
}
ordering.pb(u);
}
void dfs2(vector g[], int u)
{
used[u] = true;
for(int i=0; i<g[u].size(); i++)
{
if(!used[g[u][i]])
dfs2(g,g[u][i]);
}
}
int main()
{
int t;
cin >> t;
while(t–)
{
vector g[N];
int n,m;
cin >> n >> m;
ordering.clear();
for(int i=0; i<m; i++)
{
int a,b;
cin >> a >> b;
a–;b–;
g[a].pb(b);
}
memset(used, false, sizeof(used));
for(int i=0; i<n; i++)
{
if(!used[i])
dfs1(g,i);
}
memset(used, false, sizeof(used));
int ans = 0;
for(int i=n-1; i>=0; i--)
{
if(!used[ordering[i]])
{
ans++;
dfs2(g,ordering[i]);
}
}
cout << ans << endl;
}
}