INDEP - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3

Author: Prashant Shishodia
Tester: Rahul Dugar
Editorialist: Aman Dwivedi

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Graph Theory

PROBLEM:

You are given a graph G with N vertices (numbered 1 through N) and M edges. You should partition the vertices of G into two sets A and B such that:

  • each vertex of G belongs to exactly one of these sets
  • A is non-empty
  • A is an independent set in G, i.e. for each pair of vertices u, v \in A, G does not contain an edge (u, v)
  • for each vertex a \in A and each vertex b \in B, there is an edge (a, b) in G

Find the number of such partitions (A, B). Also, give an example of one of these partitions or determine that no such partition exists.

Two partitions are considered different if there is a vertex that is in the set A in one partition and the set B in the other partition.

QUICK EXPLANATION:

  • Group all the vertices that have the same set of neighbors.

  • Now a partition is valid if, A is one of such groups, and B is their neighbor set.

  • We can store all groups in map<vector<int>, vector<int> >.

  • Count the groups such that the sum of its size and the size of neighbors set is N and output any one such group.

EXPLANATION:

The idea is to group all the vertices that have the same set of neighbors. Since only those groups can be valid.

Why ?

Suppose there are two vertices X and Y such that the neighboring set for vertex X is S_x= [V_1, V_2, \dots, V_x] and the neighboring set for vertex Y be S_y = [V_1, V_2, \dots, V_y] such that S_x \neq S_y. It means that there exists some vertex Z, such that it is either the neighbor of vertex X or vertex Y but not of both.

Now, as X and Y are in the same group. Since all vertices should share an edge with every vertex that is in the group B, hence both X and Y needs to be neighbor of vertex Z. This
cleary violates our assumption.

Hence, only those groups can be valid which have the same set of neighbors.

Claim: All such groups are Independent Set.

Proof

Let’s prove this by contradiction:

Assume that there exists a group A such that all the vertices of a group A have the same neighboring set and the group A is not an independent set.

It means there exists a pair of vertices (u, v) such that there is an edge between u and v. It means the neighboring set for u will contain v as one of its neighbors. But for the neighboring set for v, it can’t contain itself (v) as one of its neighbors. Hence the neighboring sets for u and v are not the same which violates our assumption.

Hence, if there exists a group A such that all the vertices of a group A have the same neighboring set then the group A needs to be an independent set.

Now, Count the groups such that the sum of its size and the size of neighbors set is N and output any one such group.

Subtask 1:

Since the values of N, M and T are small enough, we can do this subtask by Brute force. Implementation for the same is as follows:

  • For every vertex V of the graph, place it in the group A and all its neighbors in the group B.

  • All the remaining vertices need to be placed in group A, as the vertex V won’t be sharing an edge with these vertices.

  • Finally, check whether A is an independent set and all the vertices of a group A have an edge with every vertex of the group B. If it is so then count the group and output any one such group.

Time Complexity

O(N^3) per test case

Solution
// Subtask 1
 
#include<bits/stdc++.h>
using namespace std;
 
int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
 
  int t;
  cin>>t;
 
  while(t--)
  {
    int n,m;
    cin>>n>>m;
 
    vector <int> adj[n+1];
 
    for(int i=0;i<m;i++)
    {
      int u,v;
      cin>>u>>v;
 
      adj[u].push_back(v);
      adj[v].push_back(u);
    }
 
    int count=0;
 
    string ans(n,'0');
 
    map <vector<int>,int> map1;
 
    for(int i=1;i<=n;i++)
    {
      map <int,int> check;
      check[i]=1;
 
      vector <int> group_a,group_b;
      group_a.push_back(i);
 
      for(auto itr: adj[i])
      {
        group_b.push_back(itr);
        check[itr]=1;
      }
 
      int cnt[n+1]={};
 
      for(auto ptr: group_b)
      {
        for(auto jtr: adj[ptr])
        {
          cnt[jtr]++;
        }
      }
 
      bool ok=true;
 
      for(int j=1;j<=n;j++)
      {
        if(check[j]==0 && cnt[j]==group_b.size())
        {
          for(auto itr: adj[j])
          {
            if(check[itr]==0)
            {
              ok=false;
              break;
            }
          }
        }
      }
 
      if(!ok) continue;
 
      for(int j=1;j<=n;j++)
      {
        if(check[j]==0 && cnt[j]==group_b.size())
        {
          group_a.push_back(j);
        }
      }
 
      sort(group_a.begin(),group_a.end());
 
      if(group_a.size()+group_b.size()==n && map1[group_a]==0)
      {
        count++;
        map1[group_a]=1;
        if(count==1)
        {
          for(auto itr: group_a)
          {
            ans[itr-1]='1';
          }
        }
      }
    }
 
    cout<<count<<"\n";
    cout<<ans<<"\n";
  }
 
return 0;
}

Subtask 2:

The idea Is similar, just to optimize it further we can store all groups in map<vector<int>, vector<int> > such that the neighboring set serves as the key for this map and all the group of vertices that have the same neighboring set will be mapped with this key.

Now as all the groups have the same neighboring set as well as all the groups are Independent Set. Hence for every group, we just need to check that whether the sum of the size of the group and its neighboring set is N. If it is so then count the group and output any one such group.

Time Complexity

O(N*log(N))

SOLUTIONS:

Setter

Tester
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int powm(int a, int b) {
	int res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
 
long long readInt(long long l, long long r, char endd) {
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true) {
		char g=getchar();
		if(g=='-') {
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g&&g<='9') {
			x*=10;
			x+=g-'0';
			if(cnt==0) {
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
 
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd) {
			if(is_neg) {
				x=-x;
			}
			assert(l<=x&&x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l, int r, char endd) {
	string ret="";
	int cnt=0;
	while(true) {
		char g=getchar();
		assert(g!=-1);
		if(g==endd) {
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt&&cnt<=r);
	return ret;
}
long long readIntSp(long long l, long long r) {
	return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
	return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
	return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
	return readString(l,r,' ');
}
 
int sum_n=0,sum_m=0;
void solve() {
	int n=readIntSp(1,500000),m=readIntLn(1,500000);
//	int n,m;
//	cin>>n>>m;
	sum_n+=n;
	sum_m+=m;
	map<vi,int> pp;
	vector<vi> gra(n+1);
	set<pii> te;
	fr(i,1,m) {
		int u=readIntSp(1,n),v=readIntLn(1,n);
//		int u,v;
//		cin>>u>>v;
		if(u>v)
			swap(u,v);
		assert(u!=v&&te.count({u,v})==0);
		te.insert({u,v});
		gra[u].pb(v);
		gra[v].pb(u);
	}
	fr(i,1,n) {
		sort(all(gra[i]));
		pp[gra[i]]++;
	}
	int ans=0;
	string one(n,'1');
	for(auto &i:pp)
		if(sz(i.fi)+i.se==n) {
			ans++;
			if(ans==1)
				for(int k:i.fi)
					one[k-1]='0';
		}
	if(ans==0)
		one=string(n,'0');
	cout<<ans<<"\n"<<one<<endl;
}
 
 
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(10);
	int t=readIntLn(1,500000);
//	int t=1;
//	cin>>t;
	fr(i,1,t)
		solve();
#ifdef rd
	cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}
  
Editorialist
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
 
  int t;
  cin>>t;
 
  while(t--)
  {
    int n,m;
    cin>>n>>m;
 
    vector <int> adj[n+1];
 
    for(int i=0;i<m;i++)
    {
      int u,v;
      cin>>u>>v;
 
      adj[u].push_back(v);
      adj[v].push_back(u);
    }
 
    map <vector<int>,vector<int>> grps;
 
    for(int i=1;i<=n;i++)
    {
      sort(adj[i].begin(),adj[i].end());
      grps[adj[i]].push_back(i);
    }
 
    int count=0;
    string ans(n,'1');
 
    for(auto itr: grps)
    {
      if(itr.first.size()+itr.second.size()==n)
        count++;
      else continue;
 
      if(count==1)
      {
        for(auto ptr: itr.first)
          ans[ptr-1]='0';
      }
    }
 
    if(count==0)
      ans=string(n,'0');
 
    cout<<count<<"\n";
    cout<<ans<<"\n";
  }
 
return 0;
}
  

VIDEO EDITORIAL:

8 Likes

If the key is vector, the key comparisons are not constant time anymore. How to prove that the overall time complexity is still O(N * log(N))?

6 Likes

We are inserting each adjacency list exactly once and sum of lengths of all adjacency lists is O(M). Now when you insert a new element in the map, there will be O(\log_2(N)) comparisons of vectors as there are at most N vectors in the map. Hence each element of the adjacency list will be compared O(\log_2(N)) time. And as sum of lengths of all adjacency list is O(M), the time complexity will be O(M*\log_2(N))
I hope this makes sense @johnathan79717

12 Likes

Only one test case is failing, I can’t figure out why. May someone please help.

Solution

2 Likes

For Java Solvers use TreeSet to store adjacency list and later group on the basis of it.
Else you will get TLE

1 Like

I have another approach to this problem. Since there is no edge within Set A, in the inverse graph vertices of set A will form a clique. So we have to calculate the number of connected components which are also Complete. This cal be solved just by BFS.

1 Like

But creating the inverse graph might not be a good choice when the value of N is large.

There is no need to create the inverse graph. Using the given graph we do BFS on inverse graph.

1 Like

hi,everyone
i think there is only at most two solution possible for set A for any graph,can any one tell me the example of graph where there are more than 2 solution for A ?.

3 3
1 2
1 3
2 3

1 Like

thanks

But Can you explain how we can do bfs on inverse graph without creating it.

1 Like

https://www.codechef.com/viewsolution/43185580

1 Like

I mean to say the idea in brief? Thanks for the code

1 Like

Let’s say we have a set notFound which contains the vertices which aren’t yet visited. We run a loop on i from 1 to N, if vertex i is present in notFound then we run a bfs to find all vertices reachable from i in inverse graph. So we push the vertex i into a queue. And then inside a while loop we pop a vertex ‘u’ from queue and add those vertices which are not visited yet and it’s not a neighbour of ‘u’ to the queue. Also we delete the vertices from notFound which are added into queue. It runs pretty fast on sparse graphs.

1 Like

Can someone tell me which test case I am missing/and help me in finding the bug, it is giving the wrong answer in few test cases.??? In question INDEP.


int main()
{
ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    ll t;
    cin>>t;
    while(t--)
    {
        
        ll m,n,x,y,ans=0;
        cin>>n>>m;
        vector<int>edges[n];
        map<vector<int>,int>freq;
     for(int i=0;i<m;i++)
     {
           cin>>x>>y;
           x--;
           y--;
           edges[x].push_back(y);
           edges[y].push_back(x);
     }
      for(int i=0;i<n;i++)
     {
      sort(edges[i].begin(),edges[i].end());  
     }
     
        for(int i=0;i<n;i++)
     {
           freq[edges[i]]++;
     }
      
      string a(n,'1');
     
     for(auto it:freq)
     {
          vector<int>temp = it.first;
          if(temp.size()+it.second==n  )
         {
               ans++;
         }
         
         if(ans==1)
         {
             for(int i=0;i<temp.size();i++)
             {
                   a[temp[i]]='0';
             }
         }
    
           
     }
     
if(ans==0)
{
     a=string(n,'0');
}
 
    cout<<ans<<"\n";
    cout<<a<<"\n";
                

}
    
}

Why are we writing mp[v[i]]++ for keeping count of unique adjacency list?