Count Number Of Triangle In a Graph

এই পর্বটি পড়ার আগে বিটসেট সম্পর্কে ভালো আইডিয়া থাকা জরুরী। 

 Problem:

 একটি গ্রাফ দেয়া থাকবে n < = 2000 ভার্টেক্স এবং m < = (n*(n-1))/2 এজ এর। গ্রাফটিতে কয়টি ত্রিভুজ আছে? অর্থাৎ, এমন কয়টি ভার্টেক্স সেট {u,v,w} আছে যেখানে u-v, v-w, w-u এজ দ্বারা কানেক্টেড। 

Solution:

• গ্রাফের প্রতিটি ভার্টেক্স এর এডজাসেন্সি লিস্ট টাকে বিটসেট দিয়ে রিপ্রেজেন্ট করতে হবে। অর্থাৎ, প্রতিটি নোডের জন্য একটি করে বিটসেট ডিক্লেয়ার করতে হবে। সেই নোডের সাথে যেসব নোড কানেক্টেড তার সেসব পজিশন এর বিট অন করে দিবো।

• এরপর, n^2 লুপ চালিয়ে দেখবো প্রতি জোড়া কানেক্টেড নোড (u,v) এর জন্য তাদের বিটসেটে কমন কয়টি পজিশন এর বিট অন আছে যেখানে u<v ।  অর্থাৎ, ঐ কমন নোডগুলো এদের উভয়ের সাথে কানেক্টেড। এবং কানেক্টেড হয়ে ত্রিভুজ উৎপন্ন করেছে। এই সংখ্যা এন্সার এর সাথে যোগ করবো।

• ভালোভাবে লক্ষ্য করলে দেখবে যে, এই পদ্ধতিতে প্রতিটি ত্রিভুজ ৩বার করে গণনা হয়। তাই এন্সার কে ৩ দ্বারা ভাগ দিলেই কাজ শেষ! 

এবার কোড দেখা যাকঃ 

	#include<bits/stdc++.h>
	using namespace std;
	const int x = 2005;
	bitset<x>graph[x];
	int main()
	{
	int i,j,k,n,e,u,v,ans=0;
	cin>>n>>e;
	for(i=1 ; i<=e ; i++){
	cin>>u>>v;
	graph[u][v] = 1;
	graph[v][u] = 1;
	}
	for(i=1 ; i<=n ; i++){
	for(j=i+1 ; j<=n ; j++){
	if(graph[i][j] && graph[j][i]){
	bitset<x>common;
	common = graph[i] & graph[j];
	ans += common.count();
	}
	}
	}
	ans /= 3;
	cout<<ans<<endl;
	return 0;
	}

view raw Triangle in a graph.cpp hosted with ❤ by GitHub