Участник:ZhenyaStrelkova/IM

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/IM/

#include <iostream>
#include <vector>
#include <bitset>
 
using namespace std;
 
const int max_n = 30017;
vector<pair<int, bool> > adj[max_n];
bitset<max_n> visited;
 
bool dfs(int src, int dest) {
    if (src == dest)
        return true;
    if (visited[src])
        return false;
    visited[src] = true;
    for (pair<int, bool> &pair_ : adj[src]) {
        if (pair_.second) {
            pair_.second = false;
            if (dfs(pair_.first, dest))
                return true;
            else
                pair_.second = true;
        }
    }
    return false;
}
 
int main() {
    int T, N, M;
    cin >> T;
    for (int t = 0; t < T; t++) {
        cin >> N >> M;
        for (int i = 1; i <= N; i++)
            adj[i].clear();
 
        for (int i = 0; i < M; i++) {
            int u, v;
            cin >> u >> v;
            if (u <= 0 or v <= 0 or u > N or v > N)
                continue;
            adj[u].emplace_back(v, true);
            adj[v].emplace_back(u, true);
        }
        visited.reset();
        if (!dfs(2, 1))
            cout << "NO\n";
        else {
            visited.reset();
            cout << (dfs(2, 3) ? "YES" : "NO") << "\n";
        }
    }
    return 0;
}