# CF555E Case of Computer Network题解

10/24 08:50

X=Y，不用管（由定理）

``````#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
int bridge[400005],f[400005][3],q[200005],vis[200005],dep[200005],son[200005];
struct node{

int x,y;
}a[200005];
map<int,int> h[200005];
int i,j,k,m,n,o,p,l,s,t,tot,x,y,bz,times,conum;
int low[200005],dfn[200005],co[200005],b[200005][18],mi[18],up[200005],down[200005];
void insert(int x,int y) {

f[++t][1]=y,f[t][2]=q[x],q[x]=t;}
void Tarjan(int t,int edge)
{

dfn[t]=low[t]=++tot;
for (int k=q[t];k;k=f[k][2])
{

if (!dfn[f[k][1]])
{

Tarjan(f[k][1],k);
low[t]=min(low[t],low[f[k][1]]);
if (dfn[t]<low[f[k][1]]) bridge[k]=bridge[k^1]=1;
} else if (k!=(edge^1)) low[t]=min(low[t],dfn[f[k][1]]);
}
}
void dg(int t)
{

co[t]=tot;
for (int k=q[t];k;k=f[k][2])
{

if (co[f[k][1]]||bridge[k]) continue;
dg(f[k][1]);
}
}
void dfs(int t,int fa)
{

b[t][0]=fa,vis[t]=tot,son[fa]=t,dep[t]=dep[fa]+1;
for (int i=1;i<=17;i++) b[t][i]=b[b[t][i-1]][i-1];
for (int k=q[t];k;k=f[k][2])
{

if (vis[f[k][1]]) continue;
dfs(f[k][1],t);
}
}
void getsum(int t)
{

vis[t]=1;
for (int k=q[t];k;k=f[k][2])
{

if (!vis[f[k][1]]) {

if (!bz) return;
getsum(f[k][1]);
up[t]+=up[f[k][1]],down[t]+=down[f[k][1]];
if (!bz) return;
}
if (!bz) return;
}
if (up[t]>0&&down[t]>0) {

bz=0;return;
}
if (!bz) return;
}
int getlca(int x,int y)
{

if (dep[x]<dep[y]) swap(x,y);
int k=dep[x]-dep[y];
for (int i=17;i>=0;i--)
if (k>=mi[i]) k-=mi[i],x=b[x][i];
if (x==y) return x;
for (int i=17;i>=0;i--)
if (b[x][i]!=b[y][i]) x=b[x][i],y=b[y][i];
return b[x][0];
}
{

char ch=getchar();x=0;
while (ch<'0'||ch>'9') ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-48,ch=getchar();
}
int main()
{

freopen("network.in","r",stdin);
freopen("network.out","w",stdout);
for (mi[0]=i=1;i<=17;i++) mi[i]=mi[i-1]*2;
for (i=1;i<=n;i++)
if (!dfn[i]) Tarjan(i,0);
tot=0;
for (i=1;i<=n;i++)
if (!co[i]) co[i]=++tot,dg(i);
memset(f,0,sizeof(f)),memset(q,0,sizeof(q)),t=1,conum=tot;
for (i=1;i<=m;i++) insert(co[a[i].x],co[a[i].y]),insert(co[a[i].y],co[a[i].x]);
tot=0;memset(vis,0,sizeof(vis));
for (i=1;i<=n;i++)
if (!vis[i]) tot++,dfs(i,0);
while (times--)
{

if (h[x][y]) continue;h[x][y]=1;
if (x==y) continue;
if (vis[x]!=vis[y]) {

puts("No");return 0;
}
int lca=getlca(x,y);
up[lca]--,up[x]++,down[lca]--,down[y]++;
}
memset(vis,0,sizeof(vis));
bz=1;
for (i=1;i<=conum;i++)
if (!vis[i]) getsum(i);
wyd:puts(bz?"Yes":"No");
return 0;
}
``````

0
0 收藏

0 评论
0 收藏
0