IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 游戏开发 -> 2022年PAT冬季甲级考试 25 A-3 Articulation Points -> 正文阅读

[游戏开发]2022年PAT冬季甲级考试 25 A-3 Articulation Points

A-3 Articulation Points??分数?25

In graph theory, given a connected graph?G, the vertices whose removal would disconnect?G?are known as?articulation points. For example, vertices 1, 3, 5, and 7 are the articulation points in the graph shown by the above figure (also given by the sample input).

It is a bit complicated to find the articulation points. Here you are only asked to check if a given vertex is an articulation point or not.

Input Specification:

Each input file contains one test case. For each case, the first line contains 3 positive integers:?N?(≤10^3),?M?(≤10^4), and?K?(≤100), which are the number of vertices, the number of edges, and the number of queries, respectively. Then?M?lines follow, each gives an?undirected?edge in the format:

v1 v2

where?v1?and?v2?are the two ends of an edge. Here we assume that all the vertices are numbered from?0?to?N?1. It is guaranteed that?v1?is never the same as?v2, and the graph is connected.

Finally a line of queries are given, which contains?K?vertices to be checked. The numbers in a line are separated by spaces.

Output Specification:

Output a string of?0's and?1's in a line. That is, for each query, print?1?if the given vertex is an articulation point, or?0?if not. There must be no space between the answers.

Sample Input:

10 11 8
0 1
8 7
9 7
1 2
1 3
3 5
5 7
2 4
3 4
5 6
6 7
5 2 9 1 6 3 2 7

Sample Output:

10010101

代码长度限制

16 KB

Java (javac)

时间限制

900 ms

内存限制

256 MB

其他编译器

时间限制

400 ms

内存限制

64 MB

#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
using namespace std;
vector<vector<int>> v, vv, que;
bool status[1006];
int y, z;

void recursion(int st) {
    if (vv[st].size()==0||st==y) return;
    status[st] = true;
    for (int i = 0; i < vv[st].size(); i++)
        if(status[vv[st][i]] ==false&& vv[st][i]!=y) recursion(vv[st][i]);
}
int main() {
    int n, m, k, i, j;
    cin >> n >> m >> k;
    v.resize(n + 1);
    vv.resize(n + 1);
    for (i = 0; i < m; i++) {
        scanf("%d %d", &y, &z);
        vv[y].push_back(z);
        vv[z].push_back(y);
    }
    for (i = 0; i < k; i++) {
        cin >> y;
        fill(status, status + 1006, false);
        status[y] = true;
        if(y!=0) recursion(0);
        else recursion((y+1)%m);
        int res = -9;
        for (j = 0; j < n; j++) {
            if (j!= y && status[j] == false) {
                res = 9;
                break;
            }
        }
        if (res > 0) cout << "1";
        else cout << "0";
    }
    return 0;
}

  游戏开发 最新文章
6、英飞凌-AURIX-TC3XX: PWM实验之使用 GT
泛型自动装箱
CubeMax添加Rtthread操作系统 组件STM32F10
python多线程编程:如何优雅地关闭线程
数据类型隐式转换导致的阻塞
WebAPi实现多文件上传,并附带参数
from origin ‘null‘ has been blocked by
UE4 蓝图调用C++函数(附带项目工程)
Unity学习笔记(一)结构体的简单理解与应用
【Memory As a Programming Concept in C a
上一篇文章      下一篇文章      查看所有文章
加:2022-12-25 11:39:00  更:2022-12-25 11:41:30 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年6日历 -2024/6/17 6:37:46-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码