Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- function processData(input) {
- var temp = input.split('\n')
- var [ N, I ] = temp.shift().split(' ').map( Number )
- // generate graph
- var graph = [] // store in an array of Set [ 0 : [ 0, 1 ], 1 : [ 3, 2 ] ] (to prevent duplicate)
- var relationalMap = {} // use to remember the map { 0 : 0, 1 : 0, 2 : 1, 3 : 1 }
- for(let i = 0; i < I;i++)
- {
- var [ ast1, ast2 ] = temp.shift().split(' ').map( Number )
- // if both of the ast1 and ast2 found in the different map => group two map
- if ( relationalMap.hasOwnProperty( ast1 ) && relationalMap.hasOwnProperty( ast2 ) )
- {
- // console.log('[both found]', ast1, ast2, relationalMap)
- var graphIndex = relationalMap[ ast1 ]
- var graphIndex2 = relationalMap[ ast2 ]
- // continue if there are already in the graph
- if ( graphIndex === graphIndex2 ) continue
- // update the set from 2 to 1, and clear set 2
- for( let i of graph[ graphIndex2 ] )
- {
- graph[ graphIndex ].add( i )
- relationalMap[ i ] = graphIndex
- }
- graph[ graphIndex2 ].clear()
- }
- // if one of ast1 and ast2 found in the map
- else if ( relationalMap.hasOwnProperty( ast1 ) || relationalMap.hasOwnProperty( ast2 ) )
- {
- // console.log('[one found]', ast1, ast2, relationalMap)
- let graphIndex = relationalMap[ ast1 ] || relationalMap[ ast2 ]
- graph[ graphIndex ].add( ast1 ).add( ast2 )
- relationalMap[ ast1 ] = graphIndex
- relationalMap[ ast2 ] = graphIndex
- }
- // if ast1 ast2 not found in the map
- else if ( !relationalMap.hasOwnProperty( ast1 ) && !relationalMap.hasOwnProperty( ast2 ) )
- {
- // console.log('[not found]', ast1, ast2, relationalMap)
- let graphSet = new Set()
- graphSet.add( ast1 ).add( ast2 )
- let graphIndex = ( graph.push( graphSet ) - 1 ) + ''
- relationalMap[ ast1 ] = graphIndex
- relationalMap[ ast2 ] = graphIndex
- }
- }
- // console.log('[graph]', graph);
- // console.log('[relationalMap]', relationalMap)
- // denotes the number of permissible ways to choose a pair of astronauts.
- var ways = 0;
- for( let i = 0;i < graph.length - 1; i++)
- {
- let waysi = graph[i].size
- for( let j = i + 1; j < graph.length; j++ )
- {
- let waysj = graph[j].size
- ways += waysi * waysj
- }
- }
- // and those who is alone in their country
- let alone = N - Object.keys( relationalMap ).length
- ways += Object.keys(relationalMap).length * ( N - Object.keys(relationalMap).length )
- ways += c(alone, 2)
- console.log(ways)
- }
- function c(n, x)
- {
- let numerator = n
- for(let i = n-1;i>(n-x);i--)
- {
- numerator *= i
- }
- let denominator = x
- for(let i = x - 1 ;i>=2;i--)
- {
- denominator *= i
- }
- return numerator/denominator
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement