Directed Acyclic Graph

    1#include <bits/stdc++.h>
    2 
    3using namespace std;
    4 
    5bool dfs(int indx, vector<vector<int>> &adj, vector<bool> &vis, vector<bool> &rec){
    6    if(rec[indx]) return true;
    7    if(vis[indx]) return false;
    8    vis[indx] = true; rec[indx] = true;
    9    for(int x : adj[indx]){
    10       if(dfs(x, adj, vis, rec)) return true;
    11    }
    12    rec[indx] = false;
    13    return false;
    14}
    15int main(){
    16    ios::sync_with_stdio(0);
    17    cin.tie(0);
    18    int n;
    19    cin >> n;
    20    vector<vector<int>> adj(n);
    21    for(int i = 0; i < n; i++){
    22        for(int j = 0; j < n; j++){
    23            int x; cin >> x;
    24            if(x){
    25                adj[i].push_back(j);
    26            }
    27        }
    28    }
    29    vector<bool> vis(n), rec(n);
    30    for(int i = 0; i < n; i++){
    31        if(!vis[i] && dfs(i, adj, vis, rec)){
    32            cout << "NO" << '\n';
    33            return 0;
    34        }
    35    }
    36    cout << "YES" << '\n';
    37    return 0;
    38}