한 획의 그림 문제(오라 회로 + 및 조사집)

획수 적 인 문제
시간 제한:
3000ms | 메모리 제한:
65535 KB
난이도:
4

묘사
zyc는 어렸을 때부터 작은 게임을 좋아했는데 그중에 그림을 그리는 것도 포함된다. 그는 네가 그에게 프로그램을 써서 그림을 한 획으로 그릴 수 있는지 없는지를 판단해 달라고 부탁했다.
모든 모서리는 한 번만 그릴 수 있고 반복해서 그릴 수 없도록 했다.

입력
첫 번째 행에는 테스트 데이터의 그룹 수를 나타내는 양의 정수 N(N<=10)만 있습니다.
각 그룹의 테스트 데이터의 첫 줄에는 두 개의 정정수 P, Q(P<=1000, Q<=2000)가 있는데 각각 이 그림에 몇 개의 정점과 몇 개의 연결선이 있는지 나타낸다.(점 번호 1부터 P까지)
다음 Q 행에는 두 개의 양의 정수 A, B(0출력
연결선이 있는 경우 Yes를 내보냅니다.
조건에 맞는 연결선이 없으면 "No"를 내보냅니다.
샘플 입력

샘플 출력

No
Yes

아이디어:
오로라 회로나 통로의 성질을 만족시키면 된다. 이 연통도를 바탕으로 0개 또는 2개의 기수도 결점이 존재하면 된다.그래서 연통도인지 아닌지를 판단해 모아야 한다.

AC:

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int v, e;
int root[1005], ans[1005];

void init () {
    for (int i = 1; i <= v; ++i) {
        root[i] = i;
        ans[i] = 0;
    }
}

int Find (int x) {
    return x == root[x] ? x : root[x] = Find(root[x]);
}

int main() {

    int t;
    scanf("%d", &t);

    while (t--) {

        scanf("%d%d", &v, &e);

        init();

        while (e--) {
            int a, b, A, B;
            scanf("%d%d", &a, &b);
            ++ans[a];
            ++ans[b];
            A = Find(a);
            B = Find(b);
            root[A] = B;
        }

        int num = 0;
        for (int i = 1; i <= v; ++i) {
            if (root[i] == i) ++num;
        }

        if (num > 1) printf("No
");
        else {
            num = 0;
            for (int i = 1; i <= v; ++i) {
                if (ans[i] % 2) ++num;
            }
            if (num == 2 || !num) printf("Yes
");
            else printf("No
");
        }
    }

    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

POJ 2236 Wireless Network 간편한 검색 및 수집

The ACM (Asia Cooperated Medical team) have set up a wireless network with the lap computers, but an unexpected aftersho...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

한 획의 그림 문제(오라 회로 + 및 조사집)

좋은 웹페이지 즐겨찾기