Links
Division 1
Division 2
Division 3
Setters : Utkarsh Gupta , Ronels Macwan
Testers : Manan Grover , Samarth Gupta
Difficulty
Easy-Medium
Prerequisites
Graph Theory, DFS.
Problem
There was initially an undirected, complete and simple graph. Some
edges(M) are broken. We need to keep each node in one of the sets (X or Y), such that , all
pairwise nodes in X are not adjacent, and all nodes of X have to an edge to all nodes of
Y. We have to count the number of such possible ways to do that.
Quick Explanation
Find the connected components in the input graph (not the original one). Suppose
the size of a connected component is S. If all nodes of this component have degree
S-1 ,then in the original graph, this component of nodes was purely disconnected. No node had an edge to any other node. Hence we can keep this as set X. The remaining nodes had an edge to all of these nodes in the original graph . Hence it can act as set Y.
Explanation
Initially we had a complete graph, i.e. all the nodes are connected to all the other
nodes(except itself). Now , some of the edges are destroyed. Now we need to find the answer for this graph. We are given only the broken edges.
Can we regenerate the graph ? No. The edges in complete graph are O(N^{2}). If we go with this method, the time and memory conditions will exceed.
What can be done now ? Try to imagine what the destroyed graph would look like. For set X, we need nodes that don’t have an edge between them. Try to find the set X using the given input of broken edges. Suppose we form a new graph from the edges mentioned in the input. Let’s analyze a connected component of this graph. When will it act as set X? It can only act as set X, when all the nodes in this component have degree S-1 (S is the size of this
component).
Proof
Suppose a component C has size S. It is certain that the edges which are in our newly generated graph, are absent in the original graph(we made these from broken edges). If each node has degree S-1 , it means it is like a complete graph in itself. Each node is connected to every other node. Hence in the original graph , these subset of nodes (C) will
be disconnected. No node will have an edge to any other node of this component. So, we
can take it as set X. Using the same logic, we can say that all the nodes of this component will have an edge to all other nodes (which are not in this component). Hence we found a corresponding set Y, and we can increment the count accordingly.
Do keep in mind the case where count is 1, in this case , the set Y was empty, hence donot include it in the final answer. The components can be found by simple DFS.
Solutions
Tester’s Code (Samarth):
#include <bits/stdc++.h>
using namespace std;
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,' ');
}
void readEOF(){
assert(getchar()==EOF);
}
void dfs(vector<int> graph[], int v, int vis[], vector<int> &comp){
comp.push_back(v);
vis[v] = 1;
for(auto j : graph[v])
if(!vis[j])
dfs(graph, j, vis, comp);
}
int main() {
// your code goes here
int t;
t = readIntLn(1, 1e5);
int sumn = 0, summ = 0;
while(t--){
int n = readIntSp(2, 2e5);
int m = readIntLn(0, 3e5);
//cerr << n << " " << m << '\n';
sumn += n, summ += m;
assert(sumn <= 2e5);
assert(summ <= 5e5);
assert(m <= min(500000LL, n*1ll*(n-1)/2));
vector<int> graph[n + 1];
int i;
set<pair<int, int>> s;
int deg[n + 1] = {0};
for(i = 1 ; i <= m ; i++){
int x = readIntSp(1, n);
int y = readIntLn(1, n);
assert(x != y);
assert(s.find({min(x, y), max(x, y)}) == s.end());
s.insert({min(x, y), max(x, y)});
graph[x].push_back(y);
graph[y].push_back(x);
deg[x]++, deg[y]++;
}
int vis[n + 1] = {0};
int ans = 0, cnt = 0;
for(int i = 1 ; i <= n; i++)
if(!vis[i]){
vector<int> comp;
dfs(graph, i, vis, comp);
int ok = 1, sz = comp.size();
for(auto ele : comp)
ok = (ok&(deg[ele] == sz - 1));
ans += ok;
cnt++;
}
if(cnt == 1)
ans = 0;
cout << ans << '\n';
}
readEOF();
}
Tester’s Solution (Manan)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define asc(i,a,n) for(I i=a;i<n;i++)
#define dsc(i,a,n) for(I i=n-1;i>=a;i--)
#define forw(it,x) for(A it=(x).begin();it!=(x).end();it++)
#define bacw(it,x) for(A it=(x).rbegin();it!=(x).rend();it++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lb(x) lower_bound(x)
#define ub(x) upper_bound(x)
#define fbo(x) find_by_order(x)
#define ook(x) order_of_key(x)
#define all(x) (x).begin(),(x).end()
#define sz(x) (I)((x).size())
#define clr(x) (x).clear()
#define U unsigned
#define I long long int
#define S string
#define C char
#define D long double
#define A auto
#define B bool
#define CM(x) complex<x>
#define V(x) vector<x>
#define P(x,y) pair<x,y>
#define OS(x) set<x>
#define US(x) unordered_set<x>
#define OMS(x) multiset<x>
#define UMS(x) unordered_multiset<x>
#define OM(x,y) map<x,y>
#define UM(x,y) unordered_map<x,y>
#define OMM(x,y) multimap<x,y>
#define UMM(x,y) unordered_multimap<x,y>
#define BS(x) bitset<x>
#define L(x) list<x>
#define Q(x) queue<x>
#define PBS(x) tree<x,null_type,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define PBM(x,y) tree<x,y,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define pi (D)acos(-1)
#define md 1000000007
#define rnd randGen(rng)
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;
}
int main(){
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<I> randGen;
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
I t;
t=readInt(1,100000,'\n');
I nn=0;
I mm=0;
while(t--){
I n,m;
n=readInt(1,200000,' ');
m=readInt(0,min(300000ll,(n*(n+1))/2),'\n');
nn+=n;
mm+=m;
V(I) gr[n+1];
OS(P(I,I)) s;
asc(i,0,m){
I u,v;
u=readInt(1,n,' ');
v=readInt(1,n,'\n');
assert(u!=v);
s.insert({min(u,v),max(u,v)});
gr[u].pb(v);
gr[v].pb(u);
}
assert(sz(s)==m);
asc(i,1,n+1){
gr[i].pb(i);
}
OM(OS(I),I) mpp;
asc(i,1,n+1){
OS(I) temp;
asc(j,0,sz(gr[i])){
temp.insert(gr[i][j]);
}
mpp[temp]++;
}
I ans=0;
forw(it,mpp){
if(sz((*it).fi)==(*it).se && (*it).se!=n){
ans++;
}
}
cout<<ans<<"\n";
}
assert(nn<=200000);
assert(mm<=500000);
return 0;
}
Time Complexity
O(N)