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 collections import defaultdict
sys.setrecursionlimit(10 + 2 * 10 ** 5)

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

color = [None] * (n + 1)
for i in range(n + 1):
    color[i] = i

def root(x):
    global color

    if color[x] == x:
        return x
    return root(color[x])

memo = [None] * (n + 1)
def memo_root(x):
    global memo
    global color

    if memo[x] is not None:
        return memo[x]

    if color[x] == x:
        memo[x] = x
        return memo[x]

    memo[x] = root(color[x])
    return memo[x]

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return
    color[rx] = ry

for i in range(m):
    a, b = map(int, input().split())
    unite(a, b)

cnt = defaultdict(int)
for i in range(n):
    cnt[memo_root(i + 1)] += 1
print(max(cnt.values()))

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)
        while ans.empty()==False:
            d=ans.get()
            for j in range(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:
n,m= list(map(int, input().split())) 

import networkx as nx

G = nx.Graph()
G.add_nodes_from(range(n))
for ppp in range(m):
    i,j= list(map(int, input().split()))
    i-=1
    j-=1
    G.add_edge(i,j)   
max_size = 0
for component in nx.connected_components(G):
        if len(component) > max_size:
                
                max_size = len(component)

print(max_size)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
L = []
for i in range(M):
    A,B = map(int,input().split())
    L.append([A-1,B-1])

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())

uf = UnionFind(N)
for i in range(M):
    uf.union(L[i][0],L[i][1])
c = uf.roots()
d = uf.all_group_members()
ans = 0
for a in c:
    ans = max(ans,len(d[a]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
from collections import *
from itertools import *
import functools
import sys
import math
from decimal import *
from copy import *
from heapq import *
from fractions import *
getcontext().prec = 30
MAX = sys.maxsize
MAXN = 1000010
MOD = 10**9+7
spf = [i for i in range(MAXN)]
spf[0]=-1
def sieve():
    for i in range(2,MAXN,2):
        spf[i] = 2
    for i in range(3,int(MAXN**0.5)+1):
        if spf[i]==i:
            for j in range(i,MAXN,i):
                if spf[j]==j:
                    spf[j]=i
def fib(n,m):
    if n == 0:
        return [0, 1]
    else:
        a, b = fib(n // 2)
        c = ((a%m) * ((b%m) * 2 - (a%m)))%m
        d = ((a%m) * (a%m))%m + ((b)%m * (b)%m)%m
        if n % 2 == 0:
            return [c, d]
        else:
            return [d, c + d]
 
def charIN(x= ' '):
    return(sys.stdin.readline().strip().split(x))
 
def arrIN(x = ' '):
    return list(map(int,sys.stdin.readline().strip().split(x)))
 
def ncr(n,r):
    num=den=1
    for i in range(r):
        num = (num*(n-i))%MOD
        den = (den*(i+1))%MOD
 
    return (num*(pow(den,MOD-2,MOD)))%MOD
 
def flush():
    return sys.stdout.flush()




'''*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*'''

def bfs(v):
    q = [v]
    vis[v] = 1
    l = []
    while q:
        x = q.pop(0)
        l.append(x)
        for i in d[x]:
            if not vis[i]:
                vis[i] = 1
                q.append(i)
    return l


n,m = arrIN()
d = defaultdict(set)

for _ in range(m):
    a,b = arrIN()
    d[a].add(b)
    d[b].add(a)

vis = defaultdict(int)
cc = []
for i in range(1,n+1):
    if not vis[i]:
        cc.append(bfs(i))

cc.sort(key = lambda x:len(x))
ans = len(cc[0])
cl = len(cc[0])
t = cl
for i in cc[1:]:
    if len(i)==cl:
        continue
    cl = len(i)-t
    t+=cl
    ans+=cl
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def solve() :
    n, m = map(int, input().split())
    info = []
    member = list(range(n+1))
    member_flag = [True] * (n+1)
    for _ in range(m) :
        a, b = map(int, input().split())
        if a < b :
            if not [a, b] in info :
                info.append([a, b])

        else :
            if not [b, a] in info :
                info.append([b, a])

    info.sort()

    for f in info :
        if member_flag[f[1]] :
            member[f[1]] = f[0]
            member_flag[f[1]] = False

    member.remove(0)
    cnt = Counter(member).most_common()

    print(cnt[0][1])

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n,m=INTM()
    frd=[[False]*n]
    #print(frd)
    for i in range(m):
        a,b=INTM()
        flg=True
        for k in range(len(frd)):
            if frd[k][a-1] or frd[k][b-1]:
                if not(frd[k][a-1]):
                    frd[k][a-1]=True
                if not(frd[k][b-1]):
                    frd[k][b-1]=True
                flg=False
                break
        if flg:
            temp=[False]*n
            temp[a-1]=True
            temp[b-1]=True
            frd.append(temp)
            
            
                
    #print(frd)
    ans=1
    for i in range(len(frd)):
        ans=max(ans,sum(frd[i]))
    
    print(ans)

                
if __name__=='__main__':
    do()

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, input().split())
F = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    F[a].append(b)
    F[b].append(a)
    
# 交友関係グループ（辞書型）
D = {}
# グループの親
parent = [-1] * N
# 訪問管理
visited = [False] * N

for root in range(N):
    if visited[root]:
        continue

    D[root] = set([root])
    # 訪問先のスタック
    stack = [root]
    # 訪問先が無くなるまで
    while stack:
        # 訪問者をポップアップ
        n = stack.pop()
        # 訪問者を訪問済み
        visited[n] = True
        # 訪問者のグループの親を設定
        parent[n] = root

        # root のフレンドをグループと訪問先に追加
        for to in F[n]:
            if visited[to]:
                continue
            D[root].add(to)
            stack.append(to)
print(max(map(len,D.values())))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
matrix = [[0] * N for _ in range(N)]

for _ in range(M):
  i, j = map(int, input().split())
  matrix[i-1][j-1] = matrix[j-1][i-1] = 1
num = 0
for i in range(N):
  num = max(num, sum(matrix[i]))

print(num+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 = map(int, input().split())
uf = UnionFind(N)

ab_list = []
ans =0
for i in range(M):
    a,b = map(int, input().split())
    a, b = a-1, b-1
    ab_list.append([a, b])

for i in range(M):
    uf.union(ab_list[i][0], ab_list[i][1])

ans = 0
ans_list = list(uf.all_group_members().values())
for i in range(len(ans_list)):
    ans = max(ans,len(ans_list[i]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import networkx as nx
from random import randint
def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    G=nx.Graph()

    if M == 0 :
        print(1)
        return

    for a, b in zip(A,B):
        G.add_edge(a, b)

    Gc = max(nx.connected_components(G), key=len)
    print(len(Gc))
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # def iterate_tokens():
    #     for line in sys.stdin:
    #         for word in line.split():
    #             yield word
    # tokens = iterate_tokens()
    while True:
        N = randint(10000, 100000)  # type: int
        M = 0 # type: int

        A = [randint(1, N) for i in range(M)]  # type: "List[int]"
        B = [randint(1, N) for i in range(M)]  # type: "List[int]"
        solve(N, M, A, B)

if __name__ == '__main__':
    main()

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 = map(int,input().split()) 
uf = UnionFind(N)
for _ in range(M):
  a, b = map(int,input().split())
  uf.union(a-1,b-1)

ans = 0
for i in list(uf.all_group_members().values()):
  ans = max(len(i),ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
from collections import *
from itertools import *
import functools
import sys
import math
from decimal import *
from copy import *
from heapq import *
from fractions import *
getcontext().prec = 30
MAX = sys.maxsize
MAXN = 1000010
MOD = 10**9+7
spf = [i for i in range(MAXN)]
spf[0]=-1
def sieve():
    for i in range(2,MAXN,2):
        spf[i] = 2
    for i in range(3,int(MAXN**0.5)+1):
        if spf[i]==i:
            for j in range(i,MAXN,i):
                if spf[j]==j:
                    spf[j]=i
def fib(n,m):
    if n == 0:
        return [0, 1]
    else:
        a, b = fib(n // 2)
        c = ((a%m) * ((b%m) * 2 - (a%m)))%m
        d = ((a%m) * (a%m))%m + ((b)%m * (b)%m)%m
        if n % 2 == 0:
            return [c, d]
        else:
            return [d, c + d]
 
def charIN(x= ' '):
    return(sys.stdin.readline().strip().split(x))
 
def arrIN(x = ' '):
    return list(map(int,sys.stdin.readline().strip().split(x)))
 
def ncr(n,r):
    num=den=1
    for i in range(r):
        num = (num*(n-i))%MOD
        den = (den*(i+1))%MOD
 
    return (num*(pow(den,MOD-2,MOD)))%MOD
 
def flush():
    return sys.stdout.flush()




'''*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*'''

def bfs(v):
    q = [v]
    vis[v] = 1
    l = []
    while q:
        x = q.pop(0)
        l.append(x)
        for i in d[x]:
            if not vis[i]:
                vis[i] = 1
                q.append(i)
    return l


n,m = arrIN()
d = defaultdict(list)

for _ in range(m):
    a,b = arrIN()
    d[a].append(b)
    d[b].append(a)

vis = defaultdict(int)
cc = []
for i in range(1,n+1):
    if not vis[i]:
        cc.append(bfs(i))

cc.sort(key = lambda x:len(x))
ans = len(cc[0])
cl = len(cc[0])
t = cl
for i in cc[1:]:
    if len(i)==cl:
        continue
    cl = len(i)-t
    t+=cl
    ans+=cl
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
N, M = map(int, input().split())
REL = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    REL[a-1].add(b-1)
    REL[b-1].add(a-1)

ans = 0
todo = []
done = set()
for s in range(N):
    if s in done:
        continue
    pdone = set()
    todo.append(s)
    while todo:
        p = todo.pop()
        pdone.add(p)
        for np in REL[p]:
            if np in pdone:
                continue
            todo.append(np)
    done |= pdone
    ans = max(ans, len(pdone))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
kankei=[]
n=list(map(int, input().split()))
check=[[True] * n[0] for i in range(n[0])]
group=[1]*n[0]
for i in range(n[1]):
    j = list(map(int, input().split()))
    if check[j[0]-1][j[1]-1] == True:
        check[j[0]-1][j[1]-1] = False
        check[j[1]-1][j[0]-1] = False
        group[j[0]-1]+=1
        group[j[1]-1]+=1
print(max(group))

Submission status: Time Limit Exceeded

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

canGroupingNum = [N-1 for _ in range(N)]
friendsList = list()

for i in range(M):
	a,b = map(int,input().split())
	if a>b:
		tmp = a
		a = b
		b = tmp
	if not [a,b] in friendsList:
		friendsList.append([a,b])
		canGroupingNum[a-1] += -1
		canGroupingNum[b-1] += -1

print(N-min(canGroupingNum))

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 = map(int,input().split())
L = [[0]*n for i in range(n)]
li = [i+1 for i in range(n)]
uf = UnionFind(n)

for i in range(m):
    a,b = map(int,input().split())
    L[a-1][b-1] = 1
    L[b-1][a-1] = 1
    uf.union(a-1,b-1)

ans = 0
for i in range(n):
    ans = max(ans,uf.size(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    C = []
    F = [[0]*(N+1) for i in range(N+1)]
    A = [1]*(N+1)

    for i in range(M):
        a, b = map(int, input().split())
        if F[a][b] == 0:
            F[a][b] += 1
            A[a] += 1
        if F[b][a] == 0:
            F[b][a] += 1
            A[b] += 1
    ans = max(A)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,M=[int(s) for s in input().split()] 
hito=[-1 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=[start]
  hito[start]=1
  while reach:
    _from=reach.pop(-1)
    for _to in edge[_from]:
      if not(_to in reach) and hito[_to]==-1:
        reach.append(_to)
        count+=1
        hito[_to]=1
  return(count)
 

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

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int, input().split())
f=[]
for i in range(M):
    a,b = map(int, input().split())
    for i in f:
        if a in i or b in i:
            i.add(a)
            i.add(b)
            break
    else:
        f.append(set((a,b)))

x = 0
for i in f:
    x=max(x,len(i))
if M == 0:
    x = 1
print(x)

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:[] for i in range(1,n+1)}
for i in range(m):
	x,y=map(int,input().split())
	d[x].append(y)
	d[y].append(x)


vis=set()

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:
M,N = map(int, input().split())
sets=[{m+1} for m in range(M)]
for _ in range(N):
  a,b = map(int, input().split())
  aset={}
  bset={}
  for set_ in sets:
    if a in set_:
      aset=set_
    elif b in set_:
      bset=set_
  if len(aset)!=0 and len(bset)!=0:
    newset=aset|bset
    sets.append(newset)
    sets.remove(aset)
    sets.remove(bset)
#print(sets)
max=0
for set_ in sets:
  if max < len(set_):
    max=len(set_)
print(max)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    # コンストラクタ
    def __init__(self, n):
        # 要素数
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        self.parents = [-1] * n

    # 要素xが属するグループの根を返す(経路圧縮)
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # 要素xが属するグループと要素yが属するグループとを併合する
    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

    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]

    # 要素x,yが同じグループに属するかどうかを返す
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 要素xが属するグループに属する要素をリストで返す
    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()}

N,M = map(int, input().split())
UF = UnionFind(N)

cnt = 0
for _ in range(M):
    a, b = map(int, input().split())
    UF.union(a - 1, b - 1)

ans = 0
for c in UF.all_group_members().values():
    ans = max(ans, len(c))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(10 + 2 * 10 ** 5)

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

color = [None] * (n + 1)
for i in range(n + 1):
    color[i] = i

def root(x):
    global color

    if color[x] == x:
        return x
    return root(color[x])

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return
    color[rx] = ry

for i in range(m):
    a, b = map(int, input().split())
    unite(a, b)

cnt = defaultdict(int)
for i in range(n):
    cnt[root(i + 1)] += 1
print(max(cnt.values()))

Submission status: Time Limit Exceeded

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

xs=[-1]*n

abs = set()
for _ in range(m):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    abs.add((a,b))
    abs.add((b,a))
abs = sorted(list(abs), key=lambda x:x[0])

ma = {}
for a,b in abs:
    if xs[a] == -1 and xs[b] == -1:
        min_ = min(a,b)
        xs[a] = min_
        xs[b] = min_
    elif xs[a] != -1 and xs[b] != -1:
        min_, max_ = sorted([xs[a], xs[b]])
        ma[max_] = min_
        xs = list(map(lambda x:x if ma.get(x) is None else ma[x], xs))
    else:
        new = [xs[k] for k in [a,b] if xs[k] != -1][0]
        xs[a] = new
        xs[b] = new

    # print(xs)

from collections import Counter

xs = [x for x in xs if x != -1]

if xs != []:
    print(max(Counter(xs).values()))
else:
    print(1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import connected_components
import scipy.stats as stats

n, m = map(int, input().split( ))
graph = np.array([[0]*n for _ in range(n)])
for _ in range(m):
    a, b = map(int, input().split( ))
    graph[a-1,b-1] = 1
    graph[b-1,a-1] = 1  # 有向グラフなら消す
# print(graph)

num, label = connected_components(graph)

# print(num)
# print(label)

print(stats.mode(label)[1][0])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N,M=map(int,input().split())
nums = [0]*N
n = 0
routes = []
groups = dict()
for _ in range(M):
    A,B = map(int,input().split())
    routes.append((A-1,B-1))

for i in range(M):
    a = routes[i][0]
    b = routes[i][1]
    if nums[a] == 0 and nums[b] == 0:
        n += 1
        groups[n] = {a, b}
        nums[a] = n
        nums[b] = n
    elif nums[a] == 0 and nums[b] != 0:
        nb = nums[b]
        nums[a] = nb
        groups[nb].add(a)
    elif nums[a] != 0 and nums[b] == 0:
        na = nums[a]
        nums[b] = na
        groups[na].add(b)
    elif nums[a] != nums[b]:
        na = nums[a]
        nb = nums[b]
        for num in groups[nums[b]]:
            nums[num] = na
        groups[na] = groups[na] | groups[nb]
        del groups[nb]

ans = 0
for g in groups.values():
    l = len(g)
    if l > ans:
        ans = l
print(max(ans,1))

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
A,B=[],[]

l=[-1]*N

def getID(l,idx):
  if idx==-1:
    return -1
  while True:
    if idx==l[idx]:break
    idx=l[idx]
  return idx

d={}
for i in range(M):
  s=list(map(int,input().split()))
  s[0]-=1
  s[1]-=1
  if l[s[0]]==-1 and l[s[1]]==-1:
    l[s[0]]=s[0]
    l[s[1]]=s[0]
    d[s[0]]=2
  elif l[s[0]]==-1 or l[s[1]]==-1:
    for j in range(2):
      if l[s[j]]==-1:
        id=getID(l,s[(j+1)%2])
        l[s[j]]=id
        d[id]+=1
  else:
    r1=getID(l,s[0])
    r2=getID(l,s[1])
    if r1==r2:continue
    l[r1]=r2
    d[r2]+=d[r1]
    d[r1]=0
ans=1
for i in d:
  ans=max(ans,d[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, m = map(int, input().split())
    inlis = list()
    lis1 = [[] for _ in range(n)] 
    if m == 0:
        print(1)
        exit()

    for _ in range(m):
        a, b = map(int, input().split())

        for i in range(len(lis1)):
            if len(lis1[i]) == 0:
                lis1[i].append(a)
                lis1[i].append(b)
                break
            elif a not in lis1[i] and b in lis1[i]:
                lis1[i].append(a)
                break
            elif a in lis1[i] and b not in lis1[i]:
                lis1[i].append(b)
                break
    ans = 0
    for j in range(len(lis1)):
        tmp = len(lis1[j])
        if ans < tmp:
            ans = tmp

    print(ans)
        

    

if __name__ == "__main__":
    main()

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
V = [len(v) for v in G]
print(max(V)+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N,M = map(int,input().split())

table = [[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
#    print(a,b)
    table[a].append(b)
    table[b].append(a)

visited = [0]*N
visited[0] = 1
H = deque()
H.append(0)
ans = 0
c = 1

while H:
    ans = max(ans,c)
    x = H.popleft()
#    print("x:",x,"c:",c)
#    print(visited)
    for y in table[x]:
        if visited[y] == 0:
            H.append(y)
            visited[y] = 1
#            print(y,"added")
            c += 1
    if not H:
        for i in range(N):
            if visited[i] == 0:
                H.append(i)
                visited[i] = 1
                c = 1
                break

print(ans)

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 solve():
    N, M = map(int, input().split())
    UF = UnionFind(N)
    for i in range(M):
        _a, _b = map(int, input().split())
        UF.union(_a-1, _b-1)
    rt_l = UF.roots()
    ans = 0
    for _rt in rt_l:
        _len = len(UF.members(_rt))
        if ans < _len:
            ans = _len

    print(ans)


solve()

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=[]
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.append(len(a))
print(max(grp))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
c = []
for _ in range(m):
    a, b = map(int, input().split())
    for i in c:
        if a in i or b in i:
            i.add(a)
            i.add(b)
    else:
        c.append(set())
        c[-1].add(a)
        c[-1].add(b)
if m == 0:
    print(1)
else:
    print(max(map(len, c)))

Submission status: Time Limit Exceeded

Solution code:
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]
N,M = list(map(int, input().split()))
frelist = []
for i in range(M):
  A,B = list(map(int, input().split()))
  if(B < A):
    temp = A
    A = B
    B = temp
  frelist.append([A,B])
newlist = get_unique_list(frelist)
frelist = list(newlist)
frelist.sort()

d = {}
newd = {}
for i in range(N):
  d[i+1] = []
  newd[i+1] = []
for i in range(len(frelist)):
  d[frelist[i][0]].append(frelist[i][1])
  d[frelist[i][1]].append(frelist[i][0])
#print(d)

for i in range(N):
  if(len(d[i+1])>=2):
    for j in range(len(d[i+1])):
      for k in range(j+1,len(d[i+1])):
        newd[ d[i+1][j] ].append(d[i+1][k])
        newd[ d[i+1][k] ].append(d[i+1][j])
#print(newd)

for i in range(N):
  if(len(newd[i+1])>0):
    for j in range(len(newd[i+1])):
      if(newd[i+1][j] not in d[i+1]):
        d[i+1].append(newd[i+1][j])
#print(d)

anslist = []
for i in range(N):
  anslist.append(len(d[i+1]))
print(max(anslist)+1)

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx

N, M = map(int, input().split())
#A = [0 for _ in range(M)]
#B = [0 for _ in range(M)]
C = [0 for _ in range(M)]
for i in range(M):
    #A[i], B[i] = map(int, input().split())
    C[i] = tuple(map(int, input().split()))
G = nx.Graph()
G.add_edges_from(C)
ans = 1
for comp in nx.connected_components(G):
    ans = max(ans, len(comp))

print(ans)