2022年PAT冬季甲级考试25A3ArticulationPoints

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&＃39;s and 1&＃39;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
#include
#include