Problem
Editorialist :
DIFFICULTY:
Easy Medium
PREREQUISITES
Graph, TopoSort
Problem
You are the well known video game player of your generation. You are deep diving into a newly launched video game. The game has nn levels each level is labelled by a number from 00 to n−1n−1. In the game some levels.
In the game some of level need some prerequisites i.e two integer xx, yy which means before playing the level xx you need to complete level yy.
For example the prereqsites {1,2} denotes that you need to complete level 22 to play level 11.
Explanation
In order to find weather it is possible to complete all the level or not we can check for linear ordering of the levels. Since some level have dependency factor of other level.
Hence linear ordering is only possible if we can represent all the levels in DAG that is directed acyclic graph.
Code
#include<bits/stdc++.h>
using namespace std;
#define loop(i,l,h) for(int i=(l);i<(h);i++)
#define logarr(arr,a,b) for(int z=(a);z<(b);z++) cout<<(arr[z])<<" ";cout<<endl;
#define endl "\n"
#define mod 1000000007
typedef long long int ll;
typedef long double ld;
void file_input_output(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE
}
/* ***************************************************** */
bool canFinish(int n, vector<vector<int>>& arr) {
int edges = arr.size();
vector<vector<int>> graph(n);
vector<int> indegree(n,0);
// making graph and caluculating indegree for every node
for(int i = 0; i < edges; i++){
int u = arr[i][0];
int v = arr[i][1];
graph[u].push_back(v);
indegree[v]++;
}
queue<int> q;
for(int i = 0; i < n; i++){
if(indegree[i] == 0) q.push(i);
}
int count = 0;
while(!q.empty()){
auto node = q.front();
q.pop();
count++;
for(auto it : graph[node]){
indegree[it]--;
if(indegree[it] == 0) q.push(it);
}
}
if(count == n) return true;
return false;
}
int main(){
clock_t begin=clock();
file_input_output();
int t=0;
cin>>t;t--;
do{
int n, m;
cin >> n >> m;
vector<vector<int>> graph;
for(int i = 0; i< m; i++){
vector<int> v(2);
cin >> v[0] >> v[1] ;
graph.push_back(v);
}
if(canFinish(n,graph)) cout <<"Yes" << endl;
else cout << "No" << endl;
}while(t--);
#ifndef ONLINE_JUDGE
clock_t end=clock();
cout<<"\n\nFinished in "<<double(end-begin)/CLOCKS_PER_SEC*1000<<" ms";
#endif
return 0;
}