Untitled

mail@pastecode.io avatar
unknown
plain_text
2 months ago
1.1 kB
2
Indexable
Never
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define endl "\n"
 
const double PI = 3.14159265358979;
const ll INF =  1e18 + 7;
const ll MOD = 1e9 + 7;
const ll nax = 100005;
const int LOG = 25;


bool dfs(int u, vector<int> adj[], vector<int> &col, int color) {
    col[u] = color;
    for (int v : adj[u]) {
        if (col[v] == 1) {
            if (dfs(v, adj, col, 2)) {
                return true;
            }
        } else if (col[v] == 2) {
            return true;
        }
    }
    col[u] = 3;
    return false;
}

void solve() {
    int n, m;
    cin >> n >> m;

    vector<int> adj[n + 1];
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
    }

    bool isCycle = false;
    vector<int> col(n + 1, 1);
    for (int i = 1; i <= n; i++) {
        if (col[i] == 1) {
            isCycle |= dfs(i, adj, col, 2);
        }
    }
    cout << (isCycle ? "Yes": "No") << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t; cin >> t; while(t--)
    solve();
    return 0;
}
Leave a Comment