QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#422182 | #961. Smol Vertex Cover | wdnmdwrnmmp | RE | 0ms | 0kb | C++14 | 5.0kb | 2024-05-26 21:57:59 | 2024-05-26 21:58:00 |
answer
#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef vector<int> vi;
typedef pair<int,int> pi;
const int N=505;
struct dsu{
int fa[N];
void reset(){
iota(fa, fa+N, 0);
}
int find(int d){
return d==fa[d]? d: fa[d]=find(fa[d]);
}
void merge(int u,int v){
fa[find(u)]=find(v);
}
};
void solve(){
int n,m; cin>>n>>m;
vector<vi> G(n+1);
rep(i,1,m){
int u,v; cin>>u>>v;
G[u].pb(v); G[v].pb(u);
}
dsu S;
vi match(n+1, 0);
vi col(n+1, 0), pre(n+1, 0);
vi dfn(n+1, 0);
int dfc=0;
queue<int> Q;
function<int(int,int)> LCA=[&](int u,int v){
dfc++;
u=S.find(u), v=S.find(v);
while(dfn[u]!=dfc){
dfn[u]=dfc;
u=S.find( pre[match[u]] );
if(v){
swap(u, v);
}
}
return u;
};
function<void(int,int,int)> blossom=[&](int u,int v,int lc){
while(S.find(u)!=lc){
pre[u]=v;
v=match[u];
if(col[v]==2){
col[v]=1;
Q.push(v);
}
S.fa[u]=S.fa[v]=lc;
u=pre[v];
}
};
function<void(int)> work=[&](int s){
fill(col.begin(), col.end(), 0);
fill(pre.begin(), pre.end(), 0);
S.reset();
while(!Q.empty()){
Q.pop();
}
col[s]=1;
Q.push(s);
while(!Q.empty()){
int u=Q.front(); Q.pop();
for(int v:G[u]){
if(S.find(u)==S.find(v) || col[v]==2){
continue;
}
if(!col[v]){
col[v]=2, pre[v]=u;
if(!match[v]){
for(int c=v, p; c; c=p){
p=match[pre[c]];
match[pre[c]]=c, match[c]=pre[c];
}
return;
}
else{
col[match[v]]=1;
Q.push(match[v]);
}
}
else{
int lc=LCA(u,v);
blossom(u,v,lc);
blossom(v,u,lc);
}
}
}
};
rep(i,1,n){
if(!match[i]){
work(i);
}
}
int cnt=0;
rep(i,1,n){
cnt+= (match[i]!=0);
}
cnt/=2;
function<int(int)> twosat=[&](int C){
vector<vi> G0(n+1);
rep(u,1,n){
for(int v:G[u]){
if(u==C || v==C || u<v){
continue;
}
if(!match[u]){
G0[ match[v] ].pb(v);
}
else if(!match[v]){
G0[ match[u] ].pb(u);
}
else{
G0[ match[u] ].pb(v);
G0[ match[v] ].pb(u);
}
}
}
vi dfn(n+1,0), low(n+1,0); int dfc=0;
vi bel(n+1,0); int col=0;
vi stk;
vector<vi> S;
function<void(int)> tarjan=[&](int u){
dfn[u]=low[u]=++dfc;
stk.pb(u);
for(int v:G0[u]){
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u], low[v]);
}
else if(!bel[v]){
low[u]=min(low[u], dfn[v]);
}
}
if(dfn[u]==low[u]){
col++;
S.resize(col);
int p=0;
while(p!=u){
p=stk.back();
stk.pop_back();
bel[p]=col;
S.back().pb(p);
}
}
};
rep(i,1,n){
if(!dfn[i]){
tarjan(i);
}
}
rep(i,1,n){
if(match[i] && bel[i]==bel[match[i]]){
return 0;
}
}
vector<bool> chs(n+1,0);
for(const auto &x:S){
for(int y:x){
if(match[y] && !chs[match[y]]){
chs[y]=1;
}
}
}
cout<< cnt+(C!=0) <<'\n';
rep(i,1,n){
if(chs[i] || C==i){
cout<<i<<' ';
}
}
cout<<'\n';
return 1;
};
rep(i,0,n){
if(twosat(i)){
return;
}
}
cout<<"not smol"<<'\n';
}
signed main(){
#ifndef ONLINE_JUDGE
assert(freopen(".in","r",stdin));
// assert(freopen(".out","w",stdout));
#endif
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t; cin>>t;
while(t--){
solve();
}
}
詳細信息
Test #1:
score: 0
Runtime Error
input:
5 5 1 2 2 3 3 4 4 5 1 5