Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- }
Add Comment
Please, Sign In to add comment