Problem Statement
We define the density of a non-empty simple undirected graph as $\displaystyle\frac{(\text{number of edges})}{(\text{number of vertices}) }$.
You are given positive integers $N$, $D$, and a simple undirected graph $G$ with $N$ vertices and $DN$ edges. The vertices of $G$ are numbered from $1$ to $N$, and the $i$-th edge connects vertex $A_i$ and vertex $B_i$. Determine whether $G$ satisfies the following condition.
Condition: Let $V$ be the vertex set of $G$. For any non-empty proper subset $X$ of $V$, the density of the induced subgraph of $G$ by $X$ is strictly less than $D$.
There are $T$ test cases to solve.
What is an induced subgraph?
For a vertex subset $X$ of graph $G$, the induced subgraph of $G$ by $X$ is the graph with vertex set $X$ and edge set containing all edges of $G$ that connect two vertices in $X$. In the above condition, note that we only consider vertex subsets that are neither empty nor the entire set.
Constraints
- $T \geq 1$
- $N \geq 1$
- $D \geq 1$
- The sum of $DN$ over the test cases in each input file is at most $5 \times 10^4$.
- $1 \leq A_i < B_i \leq N \ \ (1 \leq i \leq DN)$
- $(A_i, B_i) \\
eq (A_j, B_j) \ \ (1 \leq i < j \leq DN)$
Input
The input is given from Standard Input in the following format:
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
Each test case $\mathrm{case}_i \ (1 \leq i \leq T)$ is in the following format:
$N$ $D$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_{DN}$ $B_{DN}$
Output
Print $T$ lines. The $i$-th line should contain Yes if the given graph $G$ for the $i$-th test case satisfies the condition, and No otherwise.
Sample Input 1
2 3 1 1 2 1 3 twenty three 4 1 1 2 1 3 twenty three 3 4
Sample Output 1
Yes No
- The first test case is the same as Sample Input 1 in Problem D, and it satisfies the condition.
- For the second test case, the edge set of the induced subgraph by the non-empty proper subset $\{1, 2, 3\}$ of the vertex set $\{1, 2, 3, 4\ }$ is $\{(1, 2), (1, 3), (2, 3)\}$, and its density is $\displaystyle\frac{3}{3} = 1 = D $. Therefore, this graph does not satisfy the condition.
new routine
It is difficult to determine whether each subgraph meets this requirement, but move the term. \(\frac mn Content of Hall’s theorem: A bipartite graph has a full flow if and only if for any left endpoint set S, let T be all stores with edges connected to S, then \(|T|\ge |S|\ ) Then you can try to compose the picture so that judging whether \(m\) is less than or equal to \(D\) changes to judging whether there is a full flow in this bipartite graph. Split a point into \(D\) points, and then treat each edge as a point. The sum of an edge \((u,v)\) to \(u\) points \(v\) connects all the points to the edges. In this way, the full flow of this bipartite graph represents all \(m\le nD\). If you run the network flow directly, you don’t need to actually split the points. Just adjust the traffic from one point to the sink point to \(D\). But we also need to determine whether \(m\) is equal to \(nD\). The conclusion written in Editorial is to orient each edge of the original image. If the edge \(i\) in the bipartite graph flows toward the point \(u\), then from \(u\) to the point \(v\), otherwise from \(v\ \) is connected to the point \(u\). It is easy to find that the out-degree of a point is \(D\). If the resulting graph is strongly connected, then the condition holds. If there are two strongly connected components, then focus on the one with no out-degree. Since it has no out-degree, all edges are within the strongly connected block, and because each point has \(D\) out of the edge, so its density is equal to \(D\). Then we looked at whether the strongly connected component must meet the requirements and found that if there is a point set density equal to \(D\), then it has no out-degree and can only be the entire strongly connected component.
#include<bits/stdc + + .h>
using namespace std;
const int N=5e4 + 5,T=(N<<1)-1;
int t,n,d,mxf,to[N],tme,idx,dfn[N],low[N],q[N<<1],v[N<<1],hd[N<<1 ],id[N],tp,st[N];
template<int N,int M>struct graph{
int hd[N],e_num;
struct edge{
int u,v,nxt,f;
}e[M<<1];
void add_edge(int u,int v,int f)
{
e[ + + e_num]=(edge){u,v,hd[u],f};
hd[u]=e_num;
e[ + + e_num]=(edge){v,u,hd[v],0};
hd[v]=e_num;
}
void clear()
{
for(int i=2;i<=e_num;i + + )
hd[e[i].u]=0;
e_num=1;
}
};
graph<N,N>g;
graph<N<<1,N<<2>fl;
int bfs()
{
int l,r;
for(int i=0;i<=n + n*d;i + + )
fl.hd[i]=hd[i],v[i]=0;
fl.hd[T]=hd[T],v[T]=0;
v[q[l=r=1]=0]=1;
while(l<=r)
{
for(int i=fl.hd[q[l]];i;i=fl.e[i].nxt)
if(fl.e[i].f & amp; & amp;!v[fl.e[i].v])
v[q[ + + r]=fl.e[i].v]=v[q[l]] + 1;
+ + l;
}
return v[T];
}
int dfs(int x,int f)
{
if(x==T)
return f;
for(int & amp;i=fl.hd[x];i;i=fl.e[i].nxt)
{
int k;
if(fl.e[i].f & amp; & amp;v[fl.e[i].v]==v[x] + 1 & amp; & amp;(k=dfs(fl.e[ i].v,min(f,fl.e[i].f))))
{
fl.e[i].f-=k;
fl.e[i^1].f + =k;
return k;
}
}
return 0;
}
void tarjan(int x)
{
dfn[x]=low[x]= + + idx,st[ + + tp]=x;
for(int i=g.hd[x];i;i=g.e[i].nxt)
{
if(g.e[i].f & amp; & amp;!dfn[g.e[i].v])
{
tarjan(g.e[i].v);
low[x]=min(low[x],low[g.e[i].v]);
}
else if(g.e[i].f & amp; & amp;!id[g.e[i].f])
low[x]=min(low[x],dfn[g.e[i].v]);
}
if(low[x]==dfn[x])
{
+ + tme;
while(st[tp]^x)
id[st[tp--]]=tme;
id[st[tp--]]=tme;
}
}
int main()
{
scanf("%d", & amp;t);
while(t--)
{
g.clear(),fl.clear();
for(int i=0;i<=n*d;i + + )
dfn[i]=id[i]=0;
idx=tme=mxf=tp=0;
scanf("%d%d", & amp;n, & amp;d);
for(int i=1,u,v;i<=n*d;i + + )
{
scanf("%d%d", & amp;u, & amp;v);
g.add_edge(u,v,0);
fl.add_edge(0,i,1);
fl.add_edge(i,n*d + u,1);
to[i]=fl.e_num;
fl.add_edge(i,n*d + v,1);
}
for(int i=1;i<=n;i + + )
fl.add_edge(i + n*d,T,d);
for(int i=0;i<=n*d + n;i + + )
hd[i]=fl.hd[i];
hd[T]=fl.hd[T];
int k;
while(bfs())
while(k=dfs(0,2000000000))
mxf + =k;
if(mxf!=n*d)
{
puts("No");
continue;
}
for(int i=1;i<=n*d;i + + )
{
if(fl.e[to[i]].f)
g.e[i<<1].f=1;
else
g.e[i<<1|1].f=1;
}
for(int i=1;i<=n;i + + )
if(!dfn[i])
tarjan(i);
puts(tme^1? "No":"Yes");
}
}