246D - Colorful Graph - CodeForces Solution

brute force dfs and similar graphs *1600

Please click on ads to support us..

Python Code: 

from collections import defaultdict


def solve(n,colors,edges):
    graph=defaultdict(set)
    for u,v in edges:
        u-=1
        v-=1
        graph[colors[u]].add(colors[v])
        graph[colors[v]].add(colors[u])
    
    for i in range(n):
        graph[colors[i]].add(colors[i])
    
    ans=None
    curr=0
    for k,v in graph.items():
        if len(v)>curr:
            curr=len(v)
            ans=k
        elif len(v)==curr:
            ans=min(ans,k)
    print(ans)




n,m=map(int,input().split())
colors=list(map(int,input().split()))
edges=[]
for i in range(m):
    u,v=map(int,input().split())
    edges.append((u,v))

solve(n,colors,edges)

C++ Code: 

#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define pb push_back
#define vlli vector<long long int>
typedef long long int lli;
typedef unsigned long long int ulli;
#define vvlli vector<vector<lli> >
#define vvp vector<vector<pair<lli,lli> > >


int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lli t;
    t=1;
    // cin>>t;
    for(lli ncase=1;ncase<=t;++ncase){
        // cout<<"Case #"<<ncase<<": ";
        
        lli n,m;
        cin>>n>>m;

        lli a[n+1];

        vvlli c(100005);

        for(lli i=1;i<=n;++i){
            cin>>a[i];
            c[a[i]].push_back(i);
        }

        vvlli v(n+1);

        for(lli i=0;i<m;++i){
            lli x, y;
            cin>>x>>y;
            v[x].push_back(y);
            v[y].push_back(x);
        }

        map<lli, lli>done;

        lli vis[100005];
        memset(vis, 0, sizeof(vis));

        lli maxi=-1;
        lli ind=0;

        for(lli i=0;i<100005;++i){
            lli ans=0;
            for(auto x:c[i]){
                for(auto y:v[x]){
                    if(a[y]!=i && !vis[a[y]]){
                        ans++;
                        vis[a[y]]=1;
                    }
                }        
            }
            for(auto x:c[i]){
                for(auto y:v[x]){
                    vis[a[y]]=0;
                }        
            }
            if(c[i].size()==0)continue;
            if(maxi<ans){
                // cout<<i<<' '<<ans<<'\n';
                maxi=ans;
                ind=i;
            }
            
        }

        cout<<ind<<'\n';
        
    }
}


Comments

Submit
0 Comments
More Questions

231A - Team
479C - Exams
1030A - In Search of an Easy Problem
158A - Next Round
71A - Way Too Long Words
160A - Twins
1A - Theatre Square
1614B - Divan and a New Project
791A - Bear and Big Brother
1452A - Robot Program
344A - Magnets
96A - Football
702B - Powers of Two
1036A - Function Height
443A - Anton and Letters
1478B - Nezzar and Lucky Number
228A - Is your horseshoe on the other hoof
122A - Lucky Division
1611C - Polycarp Recovers the Permutation
432A - Choosing Teams
758A - Holiday Of Equality
1650C - Weight of the System of Nested Segments
1097A - Gennady and a Card Game
248A - Cupboards
1641A - Great Sequence
1537A - Arithmetic Array
1370A - Maximum GCD
149A - Business trip
34A - Reconnaissance 2
59A - Word