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;
}