Submission #44669216

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN = 4e5+10,MAXM = 4e5+10,INF = 1e9;

int T,n,d;
int a[MAXM],b[MAXM],x[MAXM],y[MAXM];

int s,t;
int dis[MAXN],cur[MAXN];
queue<int>q;

vector<int>g[MAXN];

struct E{
	int u,v,c,f;
}e[MAXM];
int fst[MAXN],nxt[MAXM],tot;

void Init(){
	rep(i,1,tot)nxt[i] = 0;
	rep(i,1,t)fst[i] = 0;

    tot = 0;
}

void adde(int u,int v,int c){
    e[++tot] = (E){u,v,c,0};
    nxt[tot] = fst[u];fst[u] = tot;
}
void link(int u,int v,int c){
    adde(u,v,c);adde(v,u,0);
}

int bfs(){
    fill(dis+1,dis+1+t,INF);
    dis[s] = 0;q.push(s);
    while(q.size()){
        int u = q.front();q.pop();
        for(int j=fst[u];j;j=nxt[j])if(e[j].c-e[j].f){
            int v = e[j].v;
            if(dis[v] > dis[u]+1){
                dis[v] = dis[u]+1;
                q.push(v);
            }
        }
    }
    return dis[t] != INF;
}
int dfs(int u,int f){
    if(u==t || !f)return f;
    int ret = 0;
    for(int& j=cur[u];j;j=nxt[j]){
        int v = e[j].v;
        if(dis[v] != dis[u]+1)continue;
        
        int val = dfs(v,min(f,e[j].c-e[j].f));
        ret += val,f -= val;
        e[j].f += val,e[op(j)].f -= val;

        if(!f)break;
    }
    return ret;
}

int dinic(){
    int ret = 0;
    while(bfs()){
        rep(i,1,t)cur[i] = fst[i];
        ret += dfs(s,INF);
    }
    return ret;
}

void tomin(int& x,int y){x=min(x,y);}
int dfn[MAXN],low[MAXN],ins[MAXN],st[MAXN],top,dtot,num;

void tj(int u){
	dfn[u] = low[u] = ++dtot;
	ins[u] = 1;st[++top] = u;

	for(auto v:g[u]){
		if(!dfn[v])tj(v),tomin(low[u],low[v]);
		else if(ins[v])tomin(low[u],low[v]);
	}

	if(low[u] >= dfn[u]){
		num++;
		while(1){
			int nd = st[top--];
			ins[nd] = 0;
			if(nd==u)break; 
		}
	}
}

int tj(){
	rep(i,1,n)dfn[i] = ins[i] = 0;
	top = dtot = num = 0;

	rep(i,1,n)if(!dfn[i])tj(i);
	return num;
}

//
void solve(){
	cin>>n>>d;

	rep(i,1,n)g[i].clear();

	rep(i,1,n*d){
		cin>>a[i]>>b[i];
	}

	Init();

	s = n*d+n+1,t = s+1;

	rep(i,1,n*d){
		link(s,i,1);
		
		x[i] = tot+1;
		link(i,n*d+a[i],INF);

		y[i] = tot+1;
		link(i,n*d+b[i],INF);
	}
	rep(i,1,n){
		link(n*d+i,t,d);
	}

	int ret = dinic();
	assert(ret <= n*d);

	if(ret != n*d){
		cout<<"No\n";
		return;
	}

	rep(i,1,n*d){
		if(e[x[i]].f == 1){
			g[a[i]].push_back(b[i]);
		}else{
			g[b[i]].push_back(a[i]);
		}
	}

	rep(i,1,n)assert(g[i].size() == d);
	//

	if(tj() > 1){
		cout<<"No\n";
	}else{
		cout<<"Yes\n";
	}
}

int main(){
	cin>>T;
	while(T--)solve();

    return 0;
}

Submission Info

Compile Error

In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from ./Main.cpp:1:
./Main.cpp: In function ‘void solve()’:
./Main.cpp:159:31: warning: comparison of integer expressions of different signedness: ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  159 |  rep(i,1,n)assert(g[i].size() == d);
      |                   ~~~~~~~~~~~~^~~~

Judge Result