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

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

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

#include <iostream>
#include <vector>
 
using namespace std;
 
const int maximum = 107;
vector<int> edges[maximum];
vector<int> used;
vector<int> degree;
 
void dfs(int node) {
    used[node] = 1;
    for (int i : edges[node]) {
        if (used[i])
            continue;
        dfs(i);
    }
}
 
int main() {
    int T, N, K;
    cin >> T;
 
    for (int t = 0; t < T; t++) {
        cin >> N;
        cin >> K;
        used.resize(N + 1);
        degree.resize(N + 1);
 
        for (int i = 1; i <= N; i++) {
            edges[i].clear();
        }
        degree.clear();
        used.clear();
 
        for (int i = 0; i < K; i++) {
            int s, d, m;
            cin >> s >> d >> m;
            edges[s].emplace_back(d);
            edges[d].emplace_back(s);
            degree[s] += m;
            degree[d] += m;
        }
        dfs(1);
 
        bool possible = true;
        for (int i = 1; i <= N; i++) {
            if (!used[i])
                possible = false;
        }
        if (!possible) {
            cout << "NO" << "\n";
            continue;
        }
        int odd = 0;
        for (int i = 1; i <= N; i++) {
            if (degree[i] & 1)
                odd++;
        }
 
        if (odd > 2) {
            cout << "NO" << "\n";
        } else if (odd == 0) {
            cout << "YES " << 1 << "\n";
        } else {
            int result = -1;
            for (int i = 1; i <= N; i++) {
                if (degree[i] & 1) {
                    result = i;
                    break;
                }
            }
            cout << "YES " << result << "\n";
        }
    }
 
    return 0;
}