Cities of Different Nations (Graph Theory):Breadth First Search Implementation and Combinatorics

Problem Discussion:

There are N cities numbered from 0 to N-1.Consider a country to be a set of many cities.For more clarity, all the cities in a country are somehow connected to each other.If A is a part of a country C, and B is connected to A, then B too lies in country C.  

The Prime Minister of Byteland wants to go to any two cities.The Prime Minister loves travelling and therefore, he wants to visit cities of different nations.Prime Minister, therefore, asked his Personal Assistant to calculate the number of ways of choosing two cities such that they are from different countries.

The Personal Assistant is not good in mathematics and therefore, has come to you for the answer.

Input:

The very first line contains an integer N, number of cities.The next line contains an integer P, total number of given connections.The ith line of the next P lines contains two integers Xi and Yi, meaning Xi and Yi cities are part of the same country.

Output:

Print the required answer, an integer, in a single line.

Constraints:

1<=N<=100000
0<=P<=min(N*(N+1)/2,100000)

Example:

Input:

4

2

0 1

2 3

Output:

4

Explaination:

Sets {0,1} and {2,3} form two countries.Two cities can be chosen in following ways:

city 0 and city 2

city 0 and city 3

city 1 and city 2

city 1 and city 3

Therefore, total number of ways of choosing two cities are 4.

Algorithm:

To find the required answer, we must know the number of cities in each nation.For calculating the number of cities in each nation, we can use Breadth First Search Algorithm.

Now, the if there are M nations and the total number of cities in ith nation be iCity then the required answer, Ans can be calculated as:

Solution:

/*

Problem Description:Cities of Different Nations

Submitted By

Arjun Mishra

*/

#include<iostream>

#include<vector>

#include<queue>

using namespace std;

typedef long long LL;

vector<LL> AdjList[100001];

queue<LL> Q;

LL count[100001],c=0,visited[100001]={},sum=0;

int main()

{

    LL i,N,L;

    cin>>N>>L;

    while(L--)

    {

        LL a,b;

        cin>>a>>b;

        AdjList[a].push_back(b);

        AdjList[b].push_back(a);

    } 

    //finding connected streaks

    for(i=0;i<N;i++)

    {

        LL ct=1;

        if(!visited[i])

        {

            visited[i]=1;

Q.push(i);

            while(!Q.empty())

            {

                LL temp,len;

                temp=Q.front();

                Q.pop();

                len=AdjList[temp].size();

                for(LL j=0;j<len;j++)

                {

                    if(!visited[AdjList[temp][j]])

                    {

                        ct++;

                        visited[AdjList[temp][j]]=1;

                    }   

                    Q.push(AdjList[temp][j]);

                }    

                AdjList[temp].clear();

        }

        count[c++]=ct;  

            sum+=ct;

        }    

    }

    LL ans=0;

    for(i=0;i<c;i++)

    {

        ans+=count[i]*(sum-count[i]);

    }    

    cout<<(ans/2)<<endl;

    return 0;

}