组织
solution
20分
缩环,暴力判\(DAG\)中的点两两之间连通性.
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define M 105
#define N 100005
using namespace std;
typedef long long ll;
struct graph{
int nxt,to;
}e[N];
int g[N],f[N],l[N],r[N],s[N],to[M],dfn[N],low[N],n,m,t,top,cnt;
bool a[M][M],ins[N];
queue<int> q;
inline int read(){
int ret=0;char c=getchar();
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
ret=(ret<<1)+(ret<<3)+c-'0';
c=getchar();
}
return ret;
}
inline void addedge(int x,int y){
// printf("%d %d\n",x,y);
e[++cnt].nxt=g[x];g[x]=cnt;e[cnt].to=y;
}
inline void tarjan(int u){
dfn[u]=low[u]=++cnt;
s[++top]=u;ins[u]=true;
for(int i=g[u];i;i=e[i].nxt)
if(!dfn[e[i].to]){
tarjan(e[i].to);
low[u]=min(low[u],low[e[i].to]);
}
else if(ins[e[i].to])
low[u]=min(low[u],low[e[i].to]);
if(dfn[u]==low[u])
while(s[top+1]!=u){
f[s[top]]=u;
ins[s[top--]]=false;
}
}
inline void bfs(){
int u;cnt=0;
for(int i=1;i<=n;++i)
if(!to[i]) q.push(i);
while(!q.empty()){
s[++cnt]=u=q.front();q.pop();
for(int i=g[u];i;i=e[i].nxt)
if(!(--to[e[i].to]))
q.push(e[i].to);
}
for(u=s[cnt--];cnt>=0;u=s[cnt--])
for(int i=g[u];i;i=e[i].nxt){
a[u][e[i].to]=true;
for(int j=1;j<=n;++j)
a[u][j]|=a[e[i].to][j];
}
}
inline void Aireen(){
scanf("%d",&n);
scanf("%d",&m);
for(int i=1;i<=m;++i){
scanf("%d%d",&l[i],&r[i]);
addedge(l[i],r[i]);
}
cnt=0;
for(int i=1;i<=n;++i)
if(!dfn[i]) tarjan(i);
if(n<=100){
cnt=0;
memset(g,0,sizeof(g));
for(int i=1;i<=m;++i)
if(f[l[i]]!=f[r[i]]){
addedge(f[l[i]],f[r[i]]);++to[r[i]];
}
bfs();
scanf("%d",&t);
for(int i=1,j,k;i<=t;++i){
scanf("%d%d",&j,&k);
if(f[j]==f[k]||a[f[j]][f[k]]){
puts("NO");return;
}
}
puts("YES");
printf("%d\n",m);
for(int i=1;i<=m;++i)
printf("%d %d\n",l[i],r[i]);
return;
}
scanf("%d",&t);
for(int i=1,j,k;i<=t;++i){
scanf("%d%d",&j,&k);
if(f[j]!=f[k]){
puts("NO");return;
}
}
puts("YES");
printf("%d\n",m);
for(int i=1;i<=m;++i)
printf("%d %d\n",l[i],r[i]);
}
int main(){
freopen("gplt.in","r",stdin);
freopen("gplt.out","w",stdout);
Aireen();
fclose(stdin);
fclose(stdout);
return 0;
}
100分
缩环,分块,用\(bitset\)求出所有点到这一块的点的连通性,判是否可行.
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<bitset>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define M 10000
#define N 100005
#define min(a,b) a<b?a:b
using namespace std;
typedef long long ll;
struct graph{
int nxt,to;
}e[N];
int g[N],l[N],r[N],x[N],y[N],n,m,k,cnt;
bitset<M+10> a[N];
inline int read(){
int ret=0;char c=getchar();
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
ret=(ret<<1)+(ret<<3)+c-'0';
c=getchar();
}
return ret;
}
inline void addedge(int x,int y){
e[++cnt].nxt=g[x];g[x]=cnt;e[cnt].to=y;
}
int f[N],s[N],dfn[N],low[N],top;bool ins[N];
inline void tarjan(int u){
dfn[u]=low[u]=++cnt;
s[++top]=u;ins[u]=true;
for(int i=g[u];i;i=e[i].nxt)
if(!dfn[e[i].to]){
tarjan(e[i].to);
low[u]=min(low[u],low[e[i].to]);
}
else if(ins[e[i].to])
low[u]=min(low[u],low[e[i].to]);
if(dfn[u]==low[u])
while(s[top+1]!=u){
f[s[top]]=u;
ins[s[top--]]=false;
}
}
int to[N],q[N],h,t;
inline void topo(){
int u;h=1;
for(int i=1;i<=n;++i)
if(!to[i]) q[++t]=i;
while(h<=t){
u=q[h++];
for(int i=g[u];i;i=e[i].nxt)
if(!(--to[e[i].to])) q[++t]=e[i].to;
}
}
inline void func(int b,int end){
for(int i=1;i<=n;++i)
a[i].reset();
for(int i=b;i<=end;++i)
a[i][i-b+1]=1;
for(int i=t;i;--i)
for(int j=g[q[i]];j;j=e[j].nxt)
a[q[i]]|=a[e[j].to];
}
inline void Aireen(){
n=read();m=read();
for(int i=1;i<=m;++i){
l[i]=read();r[i]=read();
addedge(l[i],r[i]);
}
cnt=0;
for(int i=1;i<=n;++i)
if(!dfn[i]) tarjan(i);
memset(g,0,sizeof(g));cnt=0;
for(int i=1;i<=m;++i)
if(f[l[i]]!=f[r[i]]){
addedge(f[l[i]],f[r[i]]);++to[r[i]];
}
topo();
k=read();
for(int i=1;i<=k;++i){
x[i]=read();y[i]=read();
if(f[x[i]]==f[y[i]]){
puts("NO");return;
}
}
for(int i=0;i*M+1<=n;++i){
func(i*M+1,(i+1)*M);
for(int j=1;j<=k;++j)
if(y[j]>i*M&&y[j]<=(i+1)*M&&a[x[j]][y[j]-i*M]){
puts("NO");return;
}
}
puts("YES");
printf("%d\n",m);
for(int i=1;i<=m;++i)
printf("%d %d\n",l[i],r[i]);
}
int main(){
freopen("gplt.in","r",stdin);
freopen("gplt.out","w",stdout);
Aireen();
fclose(stdin);
fclose(stdout);
return 0;
}