Even Edges Code

There will be only 3 cases in total

  1. if the edges are even
  2. odd edges with atleast one vertex of odd degree
  3. odd edges with no vertex of odd degree.

in 2nd case just split in 2 parts with dividing the odd degree vertex

in 3rd case divide in 3 parts

#include<bits/stdc++.h>
    using namespace std;
    int main(){
        int t;
        cin>>t;
        while (t--)
        {
           int n,m,f=0,val;
           cin>>n>>m;
           int arr[n+5];
           for(int i=0;i<=n;i++){
               arr[i]=1;
           }
           vector<vector<int>>graph(n+5);
            vector<pair<int,int>>connect;
            for(int i=0;i<m;i++){
            	int j,k;
            	cin>>j>>k;
            	graph[j].push_back(k);
            	graph[k].push_back(j);
            	connect.push_back(make_pair(k,j));
            }
            if(m%2==0){
                cout<<"1"<<endl;
                for(int i=1;i<=n;i++){
                cout<<arr[i]<<" ";
                }
                cout<<endl;
            }
            else{
                for(auto it=connect.begin();it!=connect.end();it++){
                    int u=it->first,v=it->second;
                    if(graph[u].size()%2==1){
                        val=2;
                        f=1;
                        arr[u]=2;
                        break;
                    }
                    else if(graph[v].size()%2==1){
                        f=1;
                        arr[v]=2;
                         val=2;
                        break;
                    }
                }
                if(f!=1){
                    val=3;
                    arr[connect.begin()->first]=3;
                    arr[connect.begin()->second]=2;
                }
                cout<<val<<endl;
                for(int i=1;i<=n;i++)
                {
                    cout<<arr[i]<<" ";
                }
                cout<<endl;
            }       
        }
        return 0;
    }
3 Likes

Such a great editorial.

Best editorial of all time :heart_eyes:

9 Likes

Even a 6 * cannot write a clean and self-explaining editorial like this.

3 Likes

(It was me who added the “(Unofficial)” to the title - it was originally titled just “Editorial for Even Edges” - I’m not sure if this thread was intended to be an Editorial, or a request for one).

2 Likes

Codechef Editorialist have left the chat…

5 Likes

this might be helpful (not mine) :

1 Like

@ssjgz

Hey, so you have the privilege to edit any topic ?

If yes, then why don’t I have that privilege ??

Any Regular member can edit Thread titles - I think you might not be Regular because you’ve been suspended, perhaps?

Yes, in the past . So its effect remains. Thanks for the info…

1 Like