这份是我在第 4 个测试点出问题的代码:
#include<bits/stdc++.h>
#define LL long long
#define N 2000010
using namespace std;
struct edge
{
int v,nxt;
edge(){v=nxt=0;}
}E[N];
int head[N],Esiz,In[N];
void addedge(int u,int v)
{
Esiz++;
E[Esiz].v=v;
E[Esiz].nxt=head[u];
head[u]=Esiz;
}
int End[N],T[N][26];
int Tsiz,Cnt;
int Insert(string S)
{
int rt=0,l=S.size();
for(int i=0;i<l;i++)
{
int x=S[i]-'a';
if(!T[rt][x]) T[rt][x]=++Tsiz;
rt=T[rt][x];
}
if(End[rt]) return End[rt];
return End[rt]=++Cnt;
}
int vis[N];
int dfs(int u)
{
int rtn=1;
vis[u]=1;
for(int i=head[u];i;i=E[i].nxt)
{
int v=E[i].v;
if(vis[v]) continue;
rtn+=dfs(v);
}
return rtn;
}
int main()
{
string A,B;
while(cin >> A >> B)
{
int a=Insert(A),b=Insert(B);
addedge(a,b);
addedge(b,a);
In[a]++;
In[b]++;
}
if(dfs(1)!=Cnt)
{
puts("Impossible");
return 0;
}
int Sum=0;
for(int i=1;i<=Cnt;i++)
Sum+=In[i]&1;
if((Sum==0)||(Sum==2)) puts("Possible");
else puts("Impossible");
return 0;
}
而事实上,dfs 执行的连通块大小计数理论上是没问题的。然后我就调了半天,没发现任何问题,而玄学的是把判断条件改成:
if(dfs(1)<Cnt)
}
puts("Impossible");
return 0;
}
时,AC了。
然后我觉得十分不对劲,为什么连通块计数会出问题,最后我意识到了问题:可能没有木棍。也就是说我自认为一定存在的编号为 1 的点其实是不存在的。所以连通块计数自然而然就为 1 而大于原本的 0 ,然后就WA了。
最后,其实只需要特判 Cnt==0 的情况就好了。浪费了我蛮多时间的还。这里写出来让大伙注意一下()