 # Getting WA in Rainbow Graph

My approach:

for n<=2 answer is always 0.

else

basically all the nodes that are having this condition getting satified->“every node in the subset has at least two edges of different colors” will atleast form a trio that means something like “ABC”.

So checking n*(n-1)*(n-2) trios I am assigning each trio a specific number and in a vector i am storing that given numbered trio contains which all nodes( basically it contains 3 nodes).I am also storing the trio number corresponding to each edge( lets say the trio is ABC and is numbered 5 so i am storing AB->5 BC->5 AC->5)

Then I am applying DSU

Now I am checking in which all trios 2 nodes are common and if 2 nodes are common I am appending its trio number to the same component.(For example if I have ABC as a trio and BCD as a trio ,I will add ABC and BCD in same component).

Finally I will insert the nodes of each trio which belong to the same component and compute the maximum size of the set.

I wrote a test generation code:

``````
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
int main()
{
freopen("rtest.txt","w",stdout);
ll i,j,k,t,n;
t=35;
cout << t<<"\n";
while(t--)
{
n=rand()%30;
n++;
cout << n <<"\n";
ll mat[n+1][n+1];
ll val=(n*(n-1));
val/=2;
val++;
memset(mat,0,sizeof mat);
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
k=rand()%(val);
k++;
mat[i][j]=mat[j][i]=k;
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cout << mat[i][j] << " " ;
}
cout<<"\n";
}
}
return 0;
}

``````

My submission-> https://www.codechef.com/viewsolution/13132468

I have generated 6 files and tested my code for all the cases and it passes in all these cases which were checked with an AC submission.

Can someone please tell where I am going wrong? If possible provide some testcases.

2 Likes
//