pranay_teja
10/23/2018 - 6:33 AM

CycleDetection-DirectedGraphs`

#include<bits/stdc++.h>
using namespace std;

// #Graph
// Graph is directed

// 4
// 2
// 2
// 0 1
// 0 0
// 4
// 3
// 0 1
// 1 2
// 2 3
// 3
// 3
// 0 1
// 0 2
// 1 2
// 3
// 3
// 0 1
// 1 2
// 2 0
// Output:
// Yes
// No
// No
// Yes

void DFS(vector< vector<int> > g, int s, map<int,bool> &visited, bool &cyc, map<int, bool> &Stack){
    visited[s]=true;
    Stack[s]=true;  // adding to branch Stack
    for(int i=0;i<g[s].size();i++){
        if(Stack[g[s][i]]==true){ // if present in current branch stack=cycle
            cyc=true;
            return;
        }
        if(visited[g[s][i]]!=true){
            DFS(g,g[s][i],visited,cyc,Stack);
        }
        Stack[g[s][i]]=false;   // removing from Stack after
                                // current branch DFS is complete
    }
}

bool isCyclic(vector< vector<int> > g){
    map<int,bool> visited;
    bool cyc=false;
    for(int i=0;i<g.size();i++){    // loop is not necessary if it Graph
        if(visited[i]!=true){       // is strongly connected
            map<int, bool> Stack;
            DFS(g,i,visited,cyc,Stack);
            if(cyc){
                return true;
            }
        }
    }
    return false;
}

int main(){
    // freopen("ip.txt","r",stdin);
    int t;
    cin>>t;
    while(t--){
        int v,e;
        cin>>v;
        cin>>e;
        vector< vector<int> > g(v);
        for(int i=0;i<e;i++){
            int x,y;
            cin>>x>>y;
            g[x].push_back(y);
        }
        if(isCyclic(g)){
            cout<<"Yes";
        }else{
            cout<<"No";
        }
        cout<<endl;;
    }
    return 0;
}