SNGRAPH - Editorial

Can someone explain why this code gives TLE,
but adding following code gives AC

u=rand()%n+1;
temp=u;
while(color[temp]!=temp)
{
    temp=color[temp];
}
color[u]=temp;

in this.

1 Like

If Instead of doing components-- in the dsu function , we do components-- just after calling the dsu function , it is giving a WA , does anyone know why so ?

@c_assassin, Because when parent of two nodes are same, they belong to same component, so no of component does not decrease in that case, But in your case, regardless the situation the no of components decreases.

Can anyone explain where is it that I am wrong?

  1. k \leftarrow no.\ of\ connected\ components - 1
  2. color each component with colors from 1 to k+1
  3. Create an array deg[N]
  4. create a 2d vector invr with k+1 rows where i^{th} row corresponds to i^{th} color.

For each row calculate the number of vertices with degree \in (0, invr[i].size() $-$1] populated in an array indeg[invr[i].size()] limiting number of vertices to invr[i].size() $-$1

Add these up for corresponding degrees in deg array. i.e. deg[i] = indeg[i] \forall i \in [0, invr[i].size() $-$1]
5. k \rightarrow deg[0] and do cumulative sum over deg[] and where deg[i] exceeds N-1, deg[i] \leftarrow N-1 . Output the result.
Code: http://ideone.com/keJpT2

@senbihan for the test case

1
7 8
1 2
2 3
1 3
3 4
4 5
5 6
6 7
7 5
your solution gives
0 0 5 6 6 6 6
as output but the correct output is
0 0 6 6 6 6 6
I assume the problem you are facing has to do with how you calculate the new #connectedcomponents from the older value.

1 Like

#include<stdio.h>
int find(int n,int b[][n])
{
int count=0,i,j;
for(i=1;i<n;i++)
{
if(b[0][i]==1)
{
for(j=1;j<n;j++)
{
if(b[i][j]==1)
{
b[0][j]=1;b[j][0]=1;
}
}
}
}
for(i=0;i<n;i++) if(b[0][i]!=0) count++;
int ne=0;
while(count!=(n-1))
{
for(i=1;i<n;i++)
{
if(b[0][i]==0)
{
ne++;
b[0][i]=1;b[i][0]=1;
for(j=1;j<n;j++)
{
if(b[i][j]==1)
{
b[0][j]=1;b[j][0]=1;
}
}
}
}
count=0;
for(i=0;i<n;i++) if(b[0][i]!=0) count++;
}
return ne;
}
int main()
{
int t,n,m,i,j,k,u,v;
scanf("%d",&t);
while(t–)
{
scanf("%d%d",&n,&m);
int a[n][n],b[n][n];
int d[n];
for(i=0;i<n;i++)
{
d[i]=0;
for(j=0;j<n;j++)
{
a[i][j]=0;b[i][j]=0;
}
}
for(i=0;i<m;i++)
{
scanf("%d%d",&u,&v);
a[u-1][v-1]=1;a[v-1][u-1]=1;b[u-1][v-1]=1;b[v-1][u-1]=1;
d[u-1]++;d[v-1]++;
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(d[j]<=i)
{
for(k=0;k<n;k++)
{b[j][k]=0;b[k][j]=0;}
}
}
//matrix b stores info after disconnecting the nodes
int ne=find(n,b);
printf("%d “,ne);
for(int l=0;l<n;l++)
{
for(j=0;j<n;j++)
{
b[i][j]=a[i][j];
}
}
}
printf(”\n");
}
}

Which test case is this failing?
I have taken a n*n matrix whose element is 1 if node i+1 and node j+1 are connected,0 otherwise.Now I take the given graph and isolate the noses as per given condition for all degrees<n and find how many nodes 0th node can talk to.And add an edge between 0th node and a non communicable node and increment the value of ne.Finally when 0th node can talk to all others I terminate the loop in the function and return the value of ne.

can anyone please tell any test case where I am getting WA for the following code: CodeChef: Practical coding for everyone pl help, I spent a lot of time debugging but couldnt debug.
I want to know the test case where this code is failing…please someone help

Thank you @kaiser123, Now I understood where my logic failed.

@ved33
Try this test case -
1
10 16
1 2
1 3
1 4
2 3
2 4
3 4
5 6
5 7
5 8
6 7
6 8
7 8
9 1
9 5
10 4
10 8

Sir, anybody please guide me .What I did was make an array that has degree of all elements.
I calculated ans for d=0.Then for removing dth degree till n-1, I iterate along along all the elements of degree d and reduce their connected degree by 1.If any index’s degree becomes 0 ,I incremented the answer.
Whats the problem with this approach it failed for me,
Here is my soln
https://www.codechef.com/viewsolution/13978427
Please help.

Nice editorial, well appreciated !

@kaiser123 and @arunava5
your test case is wrong
since 1,2,3 form a loop which is against the constraint given. So m is always less than n.
1
7 8
1 2
2 3
1 3
3 4
4 5
5 6
6 7
7 5
Can any one tell for which test case my code fails?CodeChef: Practical coding for everyone

@abhishekp233

It is mentioned in the problem statement that "no self loops can occur".
In the testcase I mentioned, the loop formed by nodes 1,2 and 3 is not a self loop.
So it is valid.

@kaiser123
I had used the naive approach to solve this problem (using DFS, finding no. of components; the way @senbihan did).
The test case you provided passed for my solution. Could you please take a look at my solution SNGRAPH Solution.
I got WA for this solution. Thanks in advance!

Can some please explain me how to solve this question using dfs

I used DFS and i got tle

@senbihan , even I did the same thing. It shows wrong answer. Can anyone tell why??

my submission : CodeChef: Practical coding for everyone

@kaiser123 my code gives correct answer ,i.e 0,0,6,6,6,6,6

As soon as a component gets completely separated , I decrease the total count by 1

Can someone please explain why is N= 1e5 + 5 in the solution provided in the editorial?

Someone please explain the functions in code given in editorial.I have just studied the concept of DSU and its working.Looking for implementation.

I have taken a n*n matrix whose entry is 1 if there is an edge between I+1 and j+1 node,0 otherwise.I use the way node to see how many nodes it can communicate with and add an edge between a non communicable node and increment the value of no. of edges required.

thank you senbihan :slight_smile: