Nhóm bạn

Submit solution
Points: 3.5
Time limit: 1.0s
Python 3 4.5s
Memory limit: 98M
Author:
TICHPX
Problem types
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Trong một cuộc thi lập trình quốc tế gồm \(n\) sinh viên đến từ nhiều quốc gia khác nhau cùng tham gia. Trong buổi Gala tổng kết cuộc thi để trao giải ban tổ chức muốn sắp xếp những bạn quen biết nhau ngồi cùng một khu vực. Tức là trong cùng một khu vực thì 2 người bất kỳ trong đó phải có quan hệ quen biết bắc cầu với nhau

Hai người \(a, b\) được gọi là quen biết bắc cầu nếu họ quen biết trực tiếp với nhau hoặc tồn tại \(k\) người \(x_1,x_2,...x_k\) sao cho

\(a\) quen với \(x_1\)

\(x_1\) quen với \(x_2\)

...

\(x_i\) quen với \(x_{i+1}\)

...

\(x_k\) quen với \(b\)

Ban tổ chức muốn biết phải phân làm bao nhiêu khu vực và khu vực đông nhất là bao nhiêu sinh viên. Bạn hãy lập trình tính giúp ban tổ chức nhé

Input

Dòng đầu gồm 2 số \(n,m\) trong đó \(n\) là số sinh viên còn \(m\) là số mối quan hệ quen biết \((1 \leq n\leq 10^5, 1 \leq m \leq min(n*(n+1)/2,10^6)\)

Tiếp theo \(m\) dòng mỗi dòng chứa hai số \(u, v\) khác nhau thể hiện quan hệ quen biết \(u\) quen biết \(v\) và tất nhiên \(v\) cũng quen biết \(u\) \((1 \leq u, v \leq n)\)

Output

Dòng đầu là số khu vực cần được bố trí biết rằng khu vực ít nhất cũng phải có 1 người

Dòng tiếp theo là số người của khu vực đông nhất

Ví dụ

Input

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

Output

5
3

Giải thích Có 5 khu vực

Khu vực 1 gồm các bạn 1 2 7

Khu vực 2 gồm các bạn 3 4 5

Khu vực 3 gồm các bạn 6

Khu vực 4 gồm các bạn 8 9

Khu vực 5 gồm các bạn 10

tichpx

Comments


  • 0
    NguyenVanSon_ĐTVT2_K62  commented on Oct. 26, 2022, 1:45 a.m. ← edited 
    #include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,u,v,k=0,res=0,dem;
    cin>>n>>m;
    int d[n+5]={};
    vector<int> A[n+5];
    while(m--)
    {
        cin>>u>>v;
        A[u].push_back(v);A[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
    if(d[i]==0)
    {
        k++;
        dem=1;
        d[i]=1;
        stack<int> S;
        S.push(i);
        while(S.size())
        {
            u=S.top();S.pop();
            for(int v:A[u])
            if(d[v]==0)
            {
                d[v]=1;
                dem++;
                S.push(v);
            }
        }
        if(res<dem) res=dem;
    }
    cout<<k<<" \n"<<res;
}