În orașul Nicăieri există N băieți răi. Se știe că între ei există M relații de prietenie. De-a lungul timpului, aceste prietenii au dus la apariția unor “găști”. Dacă doi băieți nu sunt prieteni dar au cel puțin un prieten comun spunem că “se cunosc”. Dacă doi băieți au cel puțin o cunoștință comună, atunci și ei se cunosc. O gașcă este un grup de băieți cu proprietatea că oricare ar fi doi băieți x și y din grup, aceștia “se cunosc”.

Cerința

Arpsod, știe exact cine este prieten cu cine și, fiind singurul băiat bun din oraș, și-a pus următoarele întrebări:
1. Câte găști există în oraș.
2. Dacă ar mai exista O SINGURĂ relație de prietenie pe lângă cele date, în câte moduri ar putea apărea aceasta, astfel încât să se obțină o gașcă cu număr maxim de membri. Pentru că numărul de moduri poate fi foarte mare, Arpsod se mulțumește cu restul împărțirii rezultatului la 666013.

Pentru că e prea ocupat să se baricadeze în casă de frica băieților răi, Arpsod vă roagă pe voi să aflați cele două răspunsuri

Date de intrare

Pe prima linie a fișierului gasti.in se vor afla două numere naturale N și M reprezentând numărul de băieți răi, respectiv numărul de relații de prietenie. Următoarele M linii vor conține câte două numere naturale x și y cu semnificația că există o relație de prietenie între băiatul x și băiatul y.

Date de ieșire

Pe singura linie a fișierului gasti.out se vor afișa două numere separate prin spațiu, primul reprezentând răspunsul pentru prima cerința iar cel de-al doilea pentru a doua cerință.

Restricții și precizări

1 ≤ N ≤ 100.000
0 ≤ M ≤ 300.000
Dacă x este prieten cu y atunci și y este prieten cu x
Toate relațiile de prietenie sunt unice
La numărarea modurilor de adaugare a unei prietenii, prietenia x y si prietenia y x coincid
Se garanteaza ca pentru 30% din teste 1 ≤ N ≤ 1000
Pentru rezolvarea corectă a primei cerințe se acordă 40% din punctajul pe testul respectiv iar pentru rezolvarea corectă a celei de-a doua cerințe se acordă 60% din punctajul pe testul respectiv
Fișierul de ieșire TREBUIE să conțină DOUĂ valori chiar dacă doriți să rezolvați o singură cerință din cele două
Arpsod înțelege cel mai bine hit-ul lui Bob Marley: “Bad Boys”

Exemplu

gasti.in

gasti.out

3 6

Explicație

Există 3 găști în oraș, formate:

Gașca 1: 1, 2, 3
Gașca 2: 4
Gașca 3: 5

Sunt 6 moduri de a face o relație de prietenie astfel încât gașca obținută să aibă număr maxim de membri

4 cu 1, 4 cu 2, 4 cu 3, 5 cu 1, 5 cu 2, 5 cu 3

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Gasti:

#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

#define Nmax 100002
#define Mod 666013

ifstream fin ( "gasti.in" );
ofstream fout ( "gasti.out" );

vector < int > G[Nmax];
int Gasca[Nmax], Members[Nmax], Cate[Nmax];

int cnt = 0;
void DFS ( int node, int gasca ){

    cnt++;
    Gasca[node] = gasca;

    vector < int > :: iterator it;
    for ( it = G[node].begin(); it != G[node].end(); ++it ){
        if ( !Gasca[*it] )
            DFS ( *it, gasca );
    }
}

int main(){

    int N, M;

    fin >> N >> M;
    for ( int i = 1; i <= M; ++i ){
        int x, y;
        fin >> x >> y;
        G[x].push_back ( y );
        G[y].push_back ( x );
    }

    int gasti = 0, max1 = -1, max2 = -1;
    for ( int i = 1; i <= N; ++i ){
        if ( !Gasca[i] ){
            cnt = 0;
            DFS ( i, ++gasti );
            Members[gasti] = cnt;
            Cate[Members[gasti]]++;

            if ( Members[gasti] > max1 ){
                max2 = max1;
                max1 = Members[gasti];
            }
            else if ( Members[gasti] > max2 )
                max2 = Members[gasti];
        }
    }

    long long x, y;
    if ( max1 != max2 ){
        x = ( 1LL * Cate[max1] * max1 ) % Mod;
        y = ( 1LL * Cate[max2] * max2 ) % Mod;
    }
    else{
        x = ( 1LL * max1 * max1 ) % Mod;
        y = ( 1LL * Cate[max1] * ( Cate[max1]-1 ) / 2 ) % Mod;
    }
    long long rez = ( x * y ) % Mod;

    fout << gasti << " " << rez;

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1462 Gasti

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1462 Gasti de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1462 Gasti