Codeforces Round #151 D : Colorful Graph

Hi All,

I will be providing editorial for one of the problem from CF #151 today.
Link of Problem: http://codeforces.com/contest/246/problem/D

Problem Statement: All the nodes are given some color between [1-1e5]. Our task is to find one color having maximum different kind of neighbors. As per my approach, I though of making a map of 100000 size. What we can do is that on getting every edge, if both vertex has different color, we can put this in our map.
Now as we want lexicographical smallest value of vertex having same cardinality, we traverse our map in sorted order of vertexes. We simple pick the one with highest cardinality and lowest vertex number.
Hope code will resolve doubts in case you have.
Implementation:

	#include <bits/stdc++.h>
	using namespace std;
	#define ll long long
	#define rep(i, start, end) for(ll i=start; i<end; i++)
	#define MAX 100005
	unordered_map<int,bool> nodes[MAX];
	int n,m;
	int c[MAX];
	int main(){
	cin>>n>>m;
	rep(i,1,n+1) cin>>c[i];
	rep(i,0,m){
	int x,y;
	cin>>x>>y;
	if(c[x]!=c[y]) nodes[c[x]][c[y]]=nodes[c[y]][c[x]]=true;
	}
	sort(c+1,c+1+n);
	int ans=c[1];
	int size=nodes[c[1]].size();
	rep(i,1,n+1){
	if(nodes[c[i]].size()>size){
	size=nodes[c[i]].size();
	ans=c[i];
	}
	}
	cout << ans << endl;
	return 0;
	}

view raw div2_151D.cpp hosted with ❤ by GitHub

Feel free to comment in case you are not able to follow up.