SNGRAPH - Editorial

PROBLEM LINK:

Practice
Contest

Author: Hussain Kara Fallah
Tester: Hasan Jaddouh
Editorialist: Sidhant Bansal

AUTHOR’S AND TESTER’S SOLUTIONS:

AUTHOR’s solution: [Here] 444
TESTER’s solution: [Here] 555

DIFFICULTY -
Medium

PREREQUISITES -
DSU (Disjoint Set Union)

PROBLEM -
Given a graph of N nodes and M edges. For all d from 0 to N - 1 calculate the minimum no. of edges that need to be added to make the graph connected, when all the edges whose at least one end point has degree less than or equal to d is deleted.

QUICK EXPLANATION -

This question requires DSU and basic graph theory. We can simulate the process in reverse order, that is from d = N - 1 to d = 0, doing DSU of components and the answer for every d is the no. of components - 1.

EXPLANATION -

Firstly we would make an array of vectors, where in the x_{th} vector we store all the nodes whose degree is x.

Observation 1 - For any disconnected graph we can easily prove that the minimum no. of edges needed to be added to make the graph connected is equal to the no. of components - 1. Suppose we have arranged the components in line from left to right. Now you can merge any two adjacent components by adding an edge. So, you will require no. of components - 1 edges to be added.

The naive approach for this question would be to loop for d from 0 to N - 1, and for each d make the new graph with the deleted edges and do multiple DFS on this new graph to count the total no. of components and then print the answer as no. of components - 1.

But this can be optimised using the second critical observation which is -

Observation 2 - If we process d in reverse order, i.e from N - 1 to 0 then it is more efficient because the edges would only be added and not destroyed, which is a feature that DSU can support. The intuition behind this method is that for each d all the edges to be deleted are a union of those that need to be deleted for d - 1 along with some other edges specific to this d. This shows us that it is actually a completely disconnected graph, i.e all the nodes have degree = 0, when d = N - 1. And as the d is decreased, more and more edges are added. Now when d moves from d = x to d = x - 1, then all the nodes having degree = x are activated and processed (in simple term the edges which have one end point as these nodes are undeleted), which can be supported by the DSU.

So for the expected solution we actually process d from N - 1 to 0 and for each d we first store the current no. of components - 1 as the answer for this d and then activate all the nodes that are in the d_{th} vector, i.e all the nodes that have degree exactly equal to d. Now we process these activated nodes, here processing a node means to join that node to all its immediate neighbours which are active using DSU and we need to constantly maintain the count of the total no. of components while performing DSU.

Refer to the given below C++ implementation for more details -

#include "bits/stdc++.h"
using namespace std;
const int N = 1e5 + 5;

vector<int> adj[N], V[N];
int deg[N], p[N], sz[N], ans[N];
bool active[N];
int components;

int par(int x){
	if(p[x] != x)	p[x] = par(p[x]);
	return p[x];
}

void dsu(int a, int b){
	int p1 = par(a), p2 = par(b);
	if(p1 == p2)	return ;
	if(sz[p1] < sz[p2])	swap(p1, p2);
	sz[p1] += sz[p2];
	p[p2] = p1;
	components--;
}

void solve(){

	for(int i = 0; i < N; i++){
		adj[i].clear();
		V[i].clear();
		deg[i] = 0;
		active[i] = 0;
	}

	int n, m, u, v;

	cin>>n>>m;
	while(m--){
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);

		deg[u]++, deg[v]++;
	}

	components = n;
	for(int i = 1; i <= n; i++){
		p[i] = i, sz[i] = 1;
		V[deg[i]].push_back(i);
	}

	for(int i = n - 1; i >= 0; i--){
		ans[i] = components - 1;
		for(auto u : V[i])	active[u] = 1;
		for(auto u : V[i]){
			for(auto v : adj[u]){
				if(active[v] == 0)	continue;
				dsu(u, v);
			}
		}
	}

	for(int i = 0; i < n; i++)	cout<<ans[i]<<" ";
	cout<<endl;
}

int main(){
	int t;
	cin>>t;
	while(t--)	solve();
}

Time Complexity -

The time complexity of an operation in DSU with path compression is \alpha(n) and the no. of times it is done is equal to the number of edges in the graph. Therefore the complexity of the solution is O((N + M) * \alpha(N)). Since the \alpha(n) is a small constant (around 4) for all practical values of N therefore it can be ignored as a constant factor also in the complexity analysis.

AUTHOR’S AND TESTER’S SOLUTIONS:

AUTHOR’s solution: [Here] 444
TESTER’s solution: [Here] 555

3 Likes

why is my solution wrong.CodeChef: Practical coding for everyone

can anyone help me with identifying whats wrong in my approach?
my code goes here…CodeChef: Practical coding for everyone

I applied the similar logic but in some other way but could not pass to get AC. I agree the above said method is much easier. But I’d like to see where my logic failed.

The basic idea is as follows, I determined all the components first with DFS, and then for each component, if there are p vertices of degree d_i, then there will be p more components when we proceed for d_i, each being separated. and if one component gets destroyed totally, there will be (k-1) more components where k is the size of the component. We can store the maximum degree for each component to check whether the component is destroyed or not! We can iterate this for d = 0 to n-1 and the answer is total components - 1.

My partner and I tried with various test cases and all passed successfully. We have even compared with some successful submissions too.
Here is the link to my submission, can anyone please tell me where my approach fails.

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