Problem:


Score : 400 points

Problem Statement

There are N persons called Person 1 through Person N.

You are given M facts that "Person A_i and Person B_i are friends." The same fact may be given multiple times.

If X and Y are friends, and Y and Z are friends, then X and Z are also friends. There is no friendship that cannot be derived from the M given facts.

Takahashi the evil wants to divide the N persons into some number of groups so that every person has no friend in his/her group.

At least how many groups does he need to make?

Constraints

2 \leq N \leq 2\times 10^5

0 \leq M \leq 2\times 10^5

1\leq A_i,B_i\leq N

A_i \neq B_i

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M

Output

Print the answer.

Sample Input 1

5 3
1 2
3 4
5 1

Sample Output 1

3

Dividing them into three groups such as \{1,3\}, \{2,4\}, and \{5\} achieves the goal.

Sample Input 2

4 10
1 2
2 1
1 2
2 1
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output 2

4

Sample Input 3

10 4
3 1
4 1
5 9
2 6

Sample Output 3

3



Sample input:
5 3
1 2
3 4
5 1


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest
import os

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


class UnionFind:
    def __init__(self, n):
        """
        コンストラクタ
        :要素数 n:
        """
        self.n = n
        # 添字x: 値yとすると・・
        #   root以外の場合： 要素xは集合yに所属する。
        #   rootの場合　　　： 集合xの要素数はy個である。(負数で保持する)
        self.parents = [-1] * n

    def getroot(self, x):
        """
        データが属するグループのID(と考えて良いはず)を取得する。
        :調査するグループ x:
        """
        # 値が負数 = ルートに到達したので、ルート木の番号を返す。
        if self.parents[x] < 0:
            return x
        else:
            # 値が正数 = ルートに到達していない場合、さらに親の情報を確認する。
            # 下の行は経路圧縮の処理。
            self.parents[x] = self.getroot(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """
        2つのデータが属するグループを結合する。
        :結合するデータ(1つ目) x:
        :結合するデータ(2つ目) y:
        """
        # 既に同じ集合に存在するなら何もせず終了。
        x = self.getroot(x)
        y = self.getroot(y)
        if x == y:
            return

        # 集合を結合する。
        # ※ここ、「要素数の大きい集合に、少ない集合を結合」しているが、こうすることで以後の「処理量を削減」するテクニックである。
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        """
        指定したグループに属するデータの数を返す。
        :調査グループ x:
        """
        # 添え字[root]には、要素数が負数で格納されている。そのため、取得する際は-反転する。
        return -self.parents[self.getroot(x)]

    def is_same(self, x, y):
        return self.getroot(x) == self.getroot(y)

    def members(self, x):
        """
        指定したグループに属するデータの一覧を返す。size()と比較して速度が圧倒的に遅いので注意。
        :調査グループ x:
        """
        root = self.getroot(x)
        return [i for i in range(self.n) if self.getroot(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


# 実装を行う関数
def resolve(test_def_name=""):
    n, m = map(int, input().split())
    ab_s = [list(map(int, input().split())) for i in range(m)]

    work_abs = []
    for ab in ab_s:
        a = min(ab[0], ab[1])
        b = max(ab[0], ab[1])
        work_abs.append([a, b])
    
    ab_s = list(map(list, set(map(tuple, work_abs))))

    uf = UnionFind(n + 1)

    for a, b in ab_s:
        uf.union(a, b)

    ans = 0
    for aaa in uf.all_group_members():
        ans = max(ans, uf.size(aaa))

    print(ans)


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """5 3
1 2
3 4
5 1"""
        output = """3"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """4 10
1 2
2 1
1 2
2 1
1 2
1 3
1 4
2 3
2 4
3 4"""
        output = """4"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """10 4
3 1
4 1
5 9
2 6"""
        output = """3"""
        self.assertIO(test_input, output)

    # 自作テストパターン
    def test_original(self):
        pass


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
class Graph(object):

    def __init__(self):
        self.neighbours = {}
    
    def add_node(self, node):
        self.neighbours[node] = []
    
    def add_edge(self, edge):
        u, v = edge
        if v not in self.neighbours[u]:
            self.neighbours[u].append(v)
        if u not in self.neighbours[u]:
            self.neighbours[v].append(u)
    
    def dfs(self, node):
        visited[node] = 1
        count = 0
        for child in self.neighbours[node]:
            if visited[child] == 0:
                count += self.dfs(child)
        return count + 1

g = Graph()
n, m = map(int, input().split())
visited = [0] * (n + 1)
for i in range(n):
    g.add_node(i + 1)
for i in range(m):
    x, y = map(int, input().split())
    g.add_edge((x, y))
ans = -1
for i in range(1, n + 1):
    if visited[i] == 0:
        ans = max(ans,g.dfs(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue

N, M = map(int, input().split())
AB = {}
for i in range(N): AB[i] = set()
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    AB[A].add(B)
    AB[B].add(A)

finish = [False] * N
q = queue.Queue()
ans = 0
for i in range(N):
    if finish[i]: continue
    q.put(i)
    group = set()
    while not q.empty():
        x = q.get()
        group.add(x)
        finish[x] = True
        for friend in AB[x]:
            if finish[friend]: continue
            q.put(friend)
    ans = max(ans, len(group))
print(ans)

Submission status: Time Limit Exceeded

Solution code:

n, m = list(map(int, input().split(" ")))

line = []
graph = [[] for _ in range(n)]

for i in range(m):
    ai, bi = list(map(int, input().split(" ")))
    ai -= 1
    bi -= 1
    graph[ai].append(bi)
    graph[bi].append(ai)


class DFS:

    def __init__(self):
        pass

    @staticmethod
    def dfs(start):
        max_size = 0
        size = 1
        stack = [start]
        tansaku_zumi = [start]
        while stack:
            ai = stack[-1]
            if graph[ai]:
                bi = graph[ai].pop()
                if bi not in tansaku_zumi:
                    stack.append(bi)
                    size += 1
                    tansaku_zumi.append(bi)
            else:
                stack.pop()
        return size, tansaku_zumi

ans = 0
tansaku_zumi_all = []
for i in range(n):
    if i not in tansaku_zumi_all:
        size, tansaku_zumi = DFS.dfs(i)
        tansaku_zumi_all.extend(tansaku_zumi)
        ans = max(ans, size)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
input = stdin.readline
def main():
    N,M=map(int, input().split())
    l =[set() for _ in range(N)]
    for _ in range(M):
        a,b=map(int, input().split())
        for s in l:
            if s:
                if a in s or b in s:
                    s.add(a)
                    s.add(b)
                    break
            else:
                s.add(a)
                s.add(b)
                break
    ans=-1
    for s in l:
        if not(s):
            break
        ans=max(ans,len(s))
    if ans==-1:
        print(1)
    else:
        print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# 接続最大クラスタのサイズが答え？
from networkx import Graph, connected_components

N, M = [int(x) for x in input().split(' ')]

list_ab = [None] * M
for i in range(M):
    a, b = [int(x) for x in input().split(' ')]
    list_ab[i] = (a, b)


G = Graph()
G.add_nodes_from(range(N))
G.add_edges_from(list_ab)

# get max connected component
max_size = 0
for component in connected_components(G):
    max_size = max(max_size, len(component))
    #     if len(component) > max_size:
    #             max_cluster = component
    #             max_size = len(max_cluster)
print(max_size)

Submission status: Time Limit Exceeded

Solution code:
from __future__ import division, print_function
import bisect
import math
import heapq
import itertools
import sys
from collections import deque
from atexit import register
from collections import Counter
from functools import reduce
sys.setrecursionlimit(100000)
if sys.version_info[0] < 3:
    from io import BytesIO as stream
else:
    from io import StringIO as stream
 
 
if sys.version_info[0] < 3:
    class dict(dict):
        """dict() -> new empty dictionary"""
        def items(self):
            """D.items() -> a set-like object providing a view on D's items"""
            return dict.iteritems(self)
 
        def keys(self):
            """D.keys() -> a set-like object providing a view on D's keys"""
            return dict.iterkeys(self)
 
        def values(self):
            """D.values() -> an object providing a view on D's values"""
            return dict.itervalues(self)
 
    input = raw_input
    range = xrange
 
    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip
 
 
def sync_with_stdio(sync=True):
    """Set whether the standard Python streams are allowed to buffer their I/O.
 
    Args:
        sync (bool, optional): The new synchronization setting.
 
    """
    global input, flush
 
    if sync:
        flush = sys.stdout.flush
    else:
        sys.stdin = stream(sys.stdin.read())
        input = lambda: sys.stdin.readline().rstrip('\r\n')
 
        sys.stdout = stream()
        register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))
        
def main():
    n,m=map(int,input().split())

    d={}
    dsu=[]
    for i in range(n):
        dsu.append(i+1)
    
    for i in range(m):
        a,b=map(int,input().split())
        
        chota=min(a,b)
        bada=max(a,b)
        a=chota
        b=bada
        for j in range(len(dsu)):
            if dsu[j]==dsu[b-1]:
                dsu[j]=dsu[a-1]
        
    
        
    d={}
    for i in dsu:
        try:
            d[i]+=1
        except:
            d[i]=1
    
    anss=[]
    for i in d:
        anss.append(d[i])
    
    print(max(anss))
    
    

    
if __name__ == '__main__':
    sync_with_stdio(False)
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

N, M = map(int, input().split())
matrix = [[0] * (N+1) for _ in range(N+1)]
ans = 0

for _ in range(M):
    link = list(map(int, input().split()))
    matrix[link[0]][link[1]] = 1
    matrix[link[1]][link[0]] = 1
    
def dfs(current_node, row, foot_prints):
    foot_prints += [current_node]
    for search_node in range(len(row[current_node])):
        if row[current_node][search_node] and search_node not in foot_prints:
            foot_prints = dfs(search_node, row, foot_prints)
    return foot_prints

tmp = []
for i in range(1, N+1):
    if i not in tmp:
        l = dfs(1, matrix, [])
        tmp.extend(l)
        ans = max(len(l), ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import connected_components
import collections
 
N, M = map(int, input().split())
ab = []
for i in range(M):
    ab.append(list(map(int,input().split())))
 
l = [[0 for _ in range(N)] for _ in range(N)]
 
for i in range(M):
    l[ab[i][0]-1][ab[i][1]-1] = 1
 
a = np.array(l)
n, labels = connected_components(a)
 
print(collections.Counter(labels).most_common()[0][1])

Submission status: Time Limit Exceeded

Solution code:
def abc177d():
    n, m = map(int, input().split())
    check = [-1] * n
    pair = []
    group_no = 0
    group = {}
    for i in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        if check[a] == check[b]:
            if check[a] == -1:
                group[group_no] = {a, b}
                check[a] = check[b] = group_no
                group_no += 1
        elif check[a] == -1:
            group[check[b]].add(a)
            check[a] = check[b]
        elif check[b] == -1:
            group[check[a]].add(b)
            check[b] = check[a]
        else:
            re = min(check[a], check[b])
            de = max(check[a], check[b])
            for v in group[de]:
                check[v] = re
            group[re] = group[re] | group[de]
            del group[de]
    max_val = 1
    for k in group:
        max_val = max(max_val,len(group[k]))
    print(max_val)
abc177d()

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
index = 1
group = [0] * (n + 1) # 何番目のグループにいるか
groups = [set()] # グループ
for i in range(m):
  a, b = map(int, input().split())
  _a = group[a]
  _b = group[b]
  if _a == 0 and _b == 0: # 新しいグループ
    group[a] = index
    group[b] = index
    groups.append({a,b})
    index += 1
  elif _a == 0: # aが新人
    group[a] = _b
    groups[_b].add(a)
  elif _b == 0: # bが新人
    group[b] = _a
    groups[_a].add(b)
  elif _a < _b: # a,bが別グループに所属:bのいるグループをaのいるグループに移行
    for g in groups[_b]:
      group[g] = _a
    groups[_a] = groups[_a] | groups[_b]
  elif _a > _b: # a,bが別グループに所属:aのいるグループをbのいるグループに移行
    for g in groups[_a]:
      group[g] = _b
    groups[_b] = groups[_b] | groups[_a]
ans = max(map(lambda g: len(g), groups))
print(max(ans,1))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n, m = list(map(int, input().split()))
friends = []
for i in range(m):
    f = list(map(int, input().split()))
    f.sort()
    if f not in friends:
        friends.append(f)

friend_map = UnionFind(n)

for f in friends:
    friend_map.union(f[0]-1, f[1]-1)

ans = 0
for i in range(n):
    tmp = friend_map.size(i)
    ans = max(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N,M=map(int,input().split())
rinsetu=[set() for _ in range(N+1)]
for i in range(M):
    a,b=map(int,(input().split()))
    rinsetu[a].add(b)
    rinsetu[b].add(a)
grp=0
color=["white"]*(N+1)
color[0]="black"
for i in range(1,N+1):
    if color[i]=="white":
        d = deque()
        d.append(i)
        a = set()
        a.add(i)
        while(d):
            k=d.popleft()
            color[k]="black"
            for j in rinsetu[k]:
                if color[j]=="white":
                    d.append(j)
                    a.add(j)
        grp=max(grp,len(a))
print(grp)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
matrix = [[0] * N for _ in range(N)]
cnt = [0] * N
for _ in range(M):
  i, j = map(int, input().split())
  if matrix[i-1][j-1] == 0:
    cnt[i-1] += 1
    cnt[j-1] += 1
  
  matrix[i-1][j-1] = matrix[j-1][i-1] = 1



print(max(cnt)+1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N,M = map(int,input().split())
AB= [list(map(int,input().split())) for _ in range(M)]

uf = UnionFind(N)

for ab in AB:
    uf.union(ab[0]-1,ab[1]-1)
uflist = list(uf.all_group_members().values())
ans = 0
for ufs in uflist:
    ans = max(ans,len(ufs))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
d = {x:-1 for x in range(1,n+1)}
gp = []

for _ in range(m):
    i,j = map(int, input().split())
    if d[i] == -1 and d[j] == -1:
        gp.append({i, j})
        d[i] = len(gp) - 1
        d[j] = len(gp) - 1
    elif d[i] == -1 and d[j] != -1:
        d[i] = d[j]
        gp[d[j]].add(i)
    elif d[i] != -1 and d[j] == -1:
        d[j] = d[i]
        gp[d[i]].add(j)
    else:
        if d[i] != d[j]:
            gp[d[i]].update(gp[d[j]])
            for item in gp[d[j]]:
                d[item] = d[i]
if m > 0:
    print(max([len(x) for x in gp]))
else:
    print(1)

Submission status: Time Limit Exceeded

Solution code:
# abc177_d.py
# https://atcoder.jp/contests/abc177_d


# [開発時用] ログ関数
def lg(value):
    flag = False
    flag = True
    if flag:
        print(str(value))


# [開発時用] exit処理
def xt(log):
    lg('★exit() - ' + str(log))
    exit()


# 本体
def get_results():

    # 引数処理部
    lines = list()
    # # 仕様でn行と決まっている場合(の例)
    # lines_count = 1
    # 先頭行のNで行数が決まる場合(の例)
    line = input()
    N, M = list(map(int, line.split()))
    # lines.append(line)
    lines_count = M
    for _ in range(lines_count):
        lines.append(input())

    # 演算部
    # S = lines[0]
    # X = int(lines[0])
    # N, M = list(map(int, lines[0].split()))
    # values = list(map(int, lines[0].split()))
    # values = list(map(int, lines[2].split()))
    # values = list()
    # for i in range(N):
    #     values.append(int(lines[i]))
    valueses = list()
    for i in range(M):
        valueses.append(list(map(int, lines[i].split())))

    # lg(N * 100 + M)
    # lg(f'valueses=[{valueses}]')

    # N人のグループ情報(ginf)を[0, 1, 2, ..., N-1]で定義。
    ginf = list(range(N))

    for values in valueses:
        A, B = values
        # ginfから両名のグループ情報を取得
        ga = ginf[A-1]
        gb = ginf[B-1]
        # 二人の属するグループが異なる場合、B君の属するグループをA君の属するグループに統合する
        if ga != gb:
            for i in range(N):
                if ginf[i] == gb:
                    ginf[i] = ga

    # 最大人数グループを認識
    ma = 0
    for g in set(ginf):
        cnt = 0
        for i in range(N):
            if ginf[i] == g:
                cnt += 1
        if ma < cnt:
            ma = cnt

    return [ma]


# 主処理
def main():
    results = get_results()

    for result in results:
        print(result)


# 起動処理
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, m = map(int, input().split())
# arr = [tuple(map(int, input().split())) for _ in range(m)]

f = {a: set() for a in range(1, n+1)}
for _ in range(m):
    x, y = map(int, input().split())
    f[x].add(y)
    f[y].add(x)

res = 0
visited = set()
stack = deque()
for i in range(1, n+1):
    if i in visited:
        continue
    visited = {i}
    stack = deque([i])
    while stack:
        c = stack.pop()
        for v in f[c]:
            if v not in visited:
                visited.add(v)
                stack.append(v)
    res = max(res, len(visited))

print(res)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
judge = [input().split() for i in range(m)]
people = list(range(1,n+1,1))

for i in judge :
  a = i[0]
  b = i[1]
  for k in range(n) :
    if people[k] == int(a) :
      people[k] = int(b)
  for j in judge :
    j[0] = j[0].replace(a,b)
    j[1] = j[1].replace(a,b)

groups = []
for i in range(n) :
  groups.append(people.count(i+1))

print(max(groups))

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())

d={}
dsu=[]
for i in range(n):
    dsu.append(i+1)
# print(dsu)
for i in range(m):
    a,b=map(int,input().split())
    
    chota=min(a,b)
    bada=max(a,b)
    a=chota
    b=bada
    for j in range(len(dsu)):
        if dsu[j]==dsu[b-1]:
            dsu[j]=dsu[a-1]
    

    # dsu.sort()
    # print(dsu)
d={}
for i in dsu:
    try:
        d[i]+=1
    except:
        d[i]=1

anss=[]
for i in d:
    anss.append(d[i])

print(max(anss))




# d2={}
# print(d,dsu)
# for i in dsu:
#     try:
#         d2[i]+=1
#     except:
#         d2[i]=1

# aam=[]
# for i in d2:
#     aam.append(d2[i])
    
# print(max(aam))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, m = map(int, input().split())

matrix = np.array([[0 for i in range(n)] for i in range(n)])
for i in range(m):
    a, b = map(int, input().split())
    matrix[a-1][b-1] = 1
    matrix[b-1][a-1] = 1

print(matrix.sum(axis=1).max()+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M=[int(s) for s in input().split()] 
hito=[0 for i in range(N)]
edge=[set() for _ in range(N)]
for i in range(M):
  a,b=[int(s) for s in input().split()]
  edge[a-1].add(b-1)
  edge[b-1].add(a-1)


def dfs(start):
  count=1
  reach=deque([start])
  hito[start]=1
  while reach:
    _from=reach.pop()
    for _to in edge[_from]:
      if not(_to in reach) and hito[_to]==0:
        reach.append(_to)
        count+=1
        hito[_to]=1
  return(count)
 

ans=set()
for h in range(N):
  if hito[h]==0:
    ans.add(dfs(h))
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
M=[1 for i in range(n)]
F=[]
for i in range(m):
    a,b=map(int,input().split())
    a,b=min(a,b),max(a,b)
    if [a,b] not in F:
        F.append([a,b])
for f in F:
    M[f[0]-1]+=1
print(max(M))

Submission status: Time Limit Exceeded

Solution code:
#ceilevenoddformula
import math
import bisect
import copy
import time
from collections import Counter
from itertools import combinations
#map(int,input().split())
#int(x) for x in input().split()
n,m=map(int,input().split())
d={i:set() for i in range(1,n+1)}
for i in range(m):
	x,y=map(int,input().split())
	d[x].add(y)
	d[y].add(x)


vis=set()
for u,v in d.items():
	d[u]=list(v)
count=0
que=[]
for i in range(1,n+1):
	if i not in vis:
		que=[]
		c=1
		vis.add(i)
		que.append(i)
		while len(que)!=0:
			x=que.pop(0)
			for j in d[x]:
				if j not in vis:
					vis.add(j)
					c+=1
					que.append(j)
		count=max(c,count)

print(count)

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools
import sys


n, m = map(int, input().split())
ans = 0
li = [[] for i in range(n)]
for i in range(len(li)):
    li[i].append(i+1)
for i in range(m):
    a, b = map(int, input().split())
    for j in li:
        if(a in j and b not in j):
            j.append(b)
        if(b in j and a not in j):
            j.append(a)
for i in li:
    ans = max(ans, len(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
n,m=map(int,input().split())
a=[[0 for i in range(n)] for j in range(n)]
for i in range(0,m):
    b,c=map(int,input().split())
    a[b-1][c-1]=1
    a[c-1][b-1]=1
re=[0 for i in range(n)]
le=[0]
for i in range(0,n):
    if re[i]==0:
        ans=queue.Queue()
        ans.put(i)
        le.append(1)
        re[i]=1
        while ans.empty()==False:
            d=ans.get()
            for j in range(d,n):
                if a[i][j]==1 and re[j]==0:
                    ans.put(j)
                    re[j]=1
                    le[-1]+=1
print(max(le))

Submission status: Time Limit Exceeded

Solution code:
import collections
import math

import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

N,M=map(int, input().split())
l=[[0 for i in range(N)]for j in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    l[a-1][b-1]=1


a = np.array(l)

n, labels = connected_components(a)

cc=collections.Counter(labels)
ans=max(cc.values())
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())

l = []  # 同値類のリスト
d = {}  # 各人がいるlのindex
tmp = 0

for i in range(M):
    A, B = map(int, input().split())
    if (d.get(A) == None) and (d.get(B) == None):
        d[A] = tmp
        d[B] = tmp
        tmp += 1
        l.append([A, B])
    elif (d.get(A) != None) and (d.get(B) == None):
        d[B] = d[A]
        l[d[A]].append(B)
    elif (d.get(A) == None) and (d.get(B) != None):
        d[A] = d[B]
        l[d[B]].append(A)
    elif d.get(A) != d.get(B):
        for n in l[d[B]]:
            d[n] = d[A]
            l[d[A]].append(n)


if M == 0:
    ans = 1
else:
    ans = 1
    for friends in l:
        ans = max(len(friends), ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
G = [[] for i in range(n)]
C = [[]for i in range(n)]
for _ in range(m):
    A, B = map(int, input().split())
    tmp = [A,B]
    tmp2 = [B,A]
    if tmp in C or tmp2 in C:
        continue
    else:
        C.append(tmp)
        G[A-1].append(B-1)
        G[B-1].append(A-1)
ans = 0
for i in range(len(G)):
    ans = max(len(set(G[i])),ans)
print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())

A = [[0]*n for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    A[a-1][b-1] = 1
    A[b-1][a-1] = 1
ans = [0]*n
for i in range(n):
    ans[i] = sum(A[i])
print(max(ans)+1)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind(): # 0インデックス
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        '''
        xとyは-=1して使う
        '''
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

if __name__ == "__main__":
    N, M = map(int, input().split()) # N人、M個の関係
    union_find = UnionFind(N)
    for _ in range(M):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        union_find.union(A, B)

    group_dict = union_find.all_group_members()
    answer = 0
    for v in group_dict.values():
        answer = max(answer, len(v))
        
    print(answer)

Submission status: Time Limit Exceeded

Solution code:

def resolve():
    import sys
    sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
    to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
    print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

    # 入力を整数に変換して受け取る
    def input_int():
        return int(input())

    def map_int_input():
        return map(int, input())

    MII = map_int_input

    def MII_split():
        return map(int, input().split())

    def MII_to_index():
        return map(to_index, input())

    def MII_split_to_index():
        return map(to_index, input().split())

    # 入力全てを整数に変換したものの配列を受け取る
    def list_int_inputs():
        return list(map(int, input()))

    LII = list_int_inputs

    def LII_split():
        return list(map(int, input().split()))

    # 2次元リスト化
    def LII_2D(rows_number):
        return [LII() for _ in range(rows_number)]

    def LII_split_2D(rows_number):
        return [LII_split() for _ in range(rows_number)]

    N, M = MII_split()
    groups = []
    for _ in range(M):
        A, B = MII_split()
        is_in_groups = False
        for group in groups:
            if A in group and B not in group:
                group.append(B)
                break
            elif B in group and A not in group:
                group.append(A)
                break
            elif A in group and B in group:
                is_in_groups = True
                break
        if not is_in_groups:
            groups.append([A, B])

    print(max([len(x) for x in groups]) if len(groups) > 0 else 1)
    
resolve()

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
lst = []
for _ in range(m):
  temp = set(map(int, input().split()))
  memo = []
  F2 = False
  for i in range(len(lst)):
    if len(temp & lst[i]) == 1:
      memo.append(i)
    if len(temp & lst[i]) == 2:
      F2 = True
  if F2:
    pass
  elif len(memo) == 2:
    lst[memo[0]] = lst[memo[0]] | lst[memo[1]]
    lst[memo[1]] = set()
  elif len(memo) == 1:
    lst[memo[0]] = lst[memo[0]] | temp
  else:
    lst.append(temp)
#print(lst)###
if len(lst) == 0:
  print(1)
  exit()
res = 0
for s in lst:
  res = max(res, len(s))
print(res)

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split(" ")))

groups = [{0}]
ma = 1
for _ in range(M):
  a, b = list(map(int, input().split(" ")))
  for group in groups:
    if a in group or b in group:
      group.add(a)
      group.add(b)
      ma = max(ma, len(group))
    else:
      s = {a, b}
      groups.append(s)

print(ma)