Help us understand the problem. What is going on with this article?

AtCoderBeginnerContest177復習&まとめ(後半)

AtCoder ABC177

2020-08-29(土)に行われたAtCoderBeginnerContest177の問題をA問題から順に考察も踏まえてまとめたものとなります.
後半ではDEの問題を扱います.前半はこちら
問題は引用して記載していますが,詳しくはコンテストページの方で確認してください.
コンテストページはこちら
公式解説PDF

D問題 Friends

問題文
人$1$から人$N$までの$N$人の人がいます。
「人$A_i$と人$B_i$は友達である」という情報が$M$個与えられます。同じ情報が複数回与えられることもあります。
$X$と$Y$が友達、かつ、$Y$と$Z$が友達ならば、$X$と$Z$も友達です。また、$M$個の情報から導くことができない友達関係は存在しません。
悪の高橋君は、この$N$人をいくつかのグループに分け、全ての人について「同じグループの中に友達がいない」という状況を作ろうとしています。
最小でいくつのグループに分ければ良いでしょうか?

友達の繋がりをたどって,何人と繋がりがあるのか(=公式解説の友達集合の要素数)を,各まとまりごとに調べていく.
友達同士を同じグループに入れないようにするためには,少なくとも一番大きい友達集合の要素数のグループが必要となり,それが出力すべき答えとなる.
実装は,人$1$から人$N$がどこかのグループに属しているかどうか確認するlistを作成して管理することで,計算の重複をしないようにしている.

abc177d.py
n, m = map(int, input().split())
set_dict = {}
chech_list = [0] * (n + 1)
for i in range(m):
    a, b = map(int, input().split())
    if a in set_dict:
        set_dict[a].add(b)
    else:
        set_dict[a] = {b}
    if b in set_dict:
        set_dict[b].add(a)
    else:
        set_dict[b] = {a}
    chech_list[a] = 1
    chech_list[b] = 1
ans = 1
for i in range(1, n + 1):
    if chech_list[i] == 0:
        continue
    count = 0
    temp_set = set_dict[i]
    while len(temp_set) > 0:
        x = temp_set.pop()
        count += 1
        chech_list[x] = 0
        for y in set_dict[x]:
            if chech_list[y] == 1:
                temp_set.add(y)
    ans = max(count, ans)
print(ans)

E問題 Coprime

問題文
$N$個の整数があります。$i$番目の数は$A_i$です。
「全ての$1 \leq i < j \leq N$について、$GCD(A_i,A_j)=1$」が成り立つとき、{$A_i$}は pairwise coprime であるといいます。
{$A_i$}が pairwise coprime ではなく、かつ、$GCD(A_1,…,A_N)=1$であるとき、{$A_i$}は setwise coprime であるといいます。
{$A_i$}が pairwise coprime、setwise coprime、そのどちらでもない、のいずれであるか判定してください。
ただし$GCD(…)$は最大公約数を表します。

素因数分解を高速でする方法が思いつかなかった.
公式解説のエラトステネスの篩みて納得.

abc177e.py
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
n = int(input())
a_list = list(map(int, input().split()))
a_list.sort()
ans2 = a_list[0]
for i in range(1, n):
    ans2 = gcd(ans2, a_list[i])
    if ans2 == 1:
        break
if ans2 != 1:
    print("not coprime")
else:
    flag = 1
    max_a = a_list[n - 1] + 1
    num_flag_list = [True] * max_a
    d_list = list(range(0, max_a))
    d_list[0] = 1
    num_flag_list[0] = num_flag_list[1] = False
    for i in range(2, int(max_a**0.5) + 1):
        if num_flag_list[i]:
            for j in range(i**2, max_a, i):
                if num_flag_list[j] == True:
                    num_flag_list[j] = False
                    d_list[j] = i
    p_set = set()
    for a in a_list:
        if a == 1:
            continue
        temp_p_set = set()
        while True:
            p = d_list[a]
            if p not in temp_p_set:
                if p in p_set:
                    flag = 0
                    break
            temp_p_set.add(p)
            p_set.add(p)
            a = a // p
            if a == 1:
                break
        if flag == 0:
            break
    if flag == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")

後半も最後まで読んでいただきありがとうございました.

takaito0423
Qiitaでは,競プロに出た問題を復習するために記事書いたり,これからプログラミン始めたりする人のために,記事を投稿していく予定です. 基本的に難しいことよくわからないですが,学習意欲はあるので,優しくアドバイスコメントもらえるととても嬉しいです. よろしくお願いいたします.
http://hawk.ci.seikei.ac.jp/kaito/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした