PROBLEM LINK:
EXPLANATION:
We want to find the number of values of X for which graph is both connected and bipartite.
Sort the edges in ascending order of their weights.
Let us remove all edges from the original graph. Now, we add edges to the graph one by one in ascending order of their weights.
Observation 1: If the graph is connected after adding i-th edge, it remains connected after additon of (i+1)-th edge. And if it is disconnected after i-th edge, it is also disconnected before addition of i-th edge.
Observation 2: If the graph is bipartite after adding i-th edge, then it is also bipartite before addition of i-th edge. And if it is non-bipartite before i-th edge, it remains non-bipartite after i edges.
From these observations, edge cases arising are :-
A.) If the given graph is disconnected, then the answer is always zero.
B.) If the given graph is bipartite, there is no upper-limit on the value of X, hence the answer is INFINITY.
METHOD-1: Binary Search on Bipartiteness and Connectivity :- The 2 observations conveniently set us up for binary search.
Let us say the graph becomes connected after u-th edge, and remains bipartite before addition of v-th edge. Ans becomes max(0,(wt[v]-wt[u]).
METHOD-2: Creating a Bipartition of the Vertices :- Say the graph becomes connected for the first time after the u-th edge (We can easily compute this by iterating over the edges and maintaining size of connected component in a DSU).
Then, we check if the current graph is bipartite. If no, then answer is zero (from Observation-2). If yes, create a bipartition of the vertices into 2 sets.
Now, we iterate and add edges from (u+1)-th to M, and for the each added edge, check if the vertices it connects belong to different sets. If no, we move to the next iteration.
If for the v-th edge, the vertices it connects belong to the same set, answer = max(0,wt[v]-wt[u]).
SOLUTION:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define iOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define pb push_back
typedef long long int lli;
const int N=100005;
int par[N],sz[N];
int mx=1;
int getpar(int node)
{
if(node==par[node])
return node;
return par[node]=getpar(par[node]);
}
void join(int a, int b)
{
a=getpar(a);
b=getpar(b);
if(a==b)
return;
if(sz[a]>sz[b])
{
par[b]=a;
sz[a]+=sz[b];
mx=max(mx,sz[a]);
}
else
{
par[a]=b;
sz[b]+=sz[a];
mx=max(mx,sz[b]);
}
return;
}
vector<vector<int> >adj(N);
int col[N];
bool visited[N],bipartite=true;
void dfs(int node, int c)
{
col[node]=c;
visited[node]=true;
for(int i=0;i<adj[node].size();++i)
{
if(!visited[adj[node][i]])
dfs(adj[node][i],1-c);
else
{
if(col[adj[node][i]]==col[node])
bipartite=false;
continue;
}
}
}
int main()
{
int test=1;
while(test--)
{
int n,m;
cin>>n>>m;
for(int i=0;i<n;++i)
{
par[i]=i; sz[i]=1; col[i]=-1;
visited[i]=false;
}
vector<pair<lli,pair<int,int> > >edges;
for(int i=0;i<m;++i)
{
int x,y;
lli w;
cin>>x>>y>>w;
x--; y--;
edges.pb({w,{x,y}});
}
sort(edges.begin(),edges.end());
bool conn=false;
lli beg=0,last=-1;
int i=0;
while(i<m)
{
int x=edges[i].ss.ff,y=edges[i].ss.ss;
if(!conn)
{
join(x,y);
if(mx==n)
conn=true;
if(conn)
{
beg=edges[i].ff;
// make the bipartition here
for(int j=0;j<=i;++j)
{
int x1=edges[j].ss.ff,y1=edges[j].ss.ss;
adj[x1].pb(y1); adj[y1].pb(x1);
}
dfs(0,0);
if(!bipartite)
{
last=edges[i].ff-1;
break;
}
}
}
if(conn)
{
if(col[x]==col[y])
{
last=edges[i].ff-1;
break;
}
}
i++;
}
if(!conn)
{
cout<<0;
exit(0);
}
if(last==-1)
{
cout<<"INFINITY";
exit(0);
}
if(last<beg)
{
cout<<0;
exit(0);
}
cout<<last-beg+1;
}
return 0;
}