#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #define maxn 4000 using namespace std; struct hh { int to,nxt; }b[maxn]; int head[maxn],dfn[maxn],low[maxn]; ,df=,de,k=,z,gd; bool vis[maxn],g[maxn]; void link(int x,int y) { b[++tot].nxt=head[x]; b[tot].to=y; head[x]=tot; } void tarjan(int x,int rt,int fa) { dfn[x]=++df;low[x]=df; vis[x]=; for (int i=head[x];i;i=b[i].nxt) { int t=b[i].to; if (t==fa) continue; if (!dfn[t]) { tarjan(t,rt,x); low[x]=min(low[x],low[t]); ;} } else if (vis[t]) low[x]=min(low[x],dfn[t]); } } void dfs(int x) { dfn[x]=k; if (g[x]) return ; z++; for (int i=head[x];i;i=b[i].nxt) { int t=b[i].to; if (g[t]&&dfn[t]!=k) gd++,dfn[t]=k; if (!dfn[t]) dfs(t); } } int main() { ; scanf ("%d",&n); ) { memset(dfn,,sizeof(dfn)); memset(b,,sizeof(b)); memset(head,,sizeof(head)); memset(low,,sizeof(low)); memset(vis,,sizeof(vis)); memset(g,,sizeof(g)); tot=,df=,de=,k=,z=,gd=; ,l=; ; ;i<=n;++i) { int x,y; scanf ("%d%d",&x,&y); link(x,y),link(y,x); l=max(max(l,x),y); } ;i<=l;++i) { de=; ); ) g[i]=; } memset(dfn,,sizeof(dfn)); ;i<=l;++i) { if (!dfn[i]&&!g[i]) { k++;z=gd=; dfs(i); ,ans2*=(z-)*z/; ) ans1++,ans2*=z; } } printf("Case %d: %d %lld\n",++cases,ans1,ans2); scanf ("%d",&n); } }
在求割点那里卡了一个多小时
因为之前都完全不知道还有根节点那边的判断啊啊啊TAT
看了好久那几句都没看懂(空想是没有用的啊少年！otz
实际上的话 画画图就差不多了 枚举多种情况
然后主要对每一块分三种情况讨论
有俩割点的时候随你怎么炸 反正炸了一个就跑另一边
有一个割点的话就设一个好了 然后那一个不要放在割点上
没有割点就很心塞了 乖乖设俩吧= =
方案的话就简单的乘一乘就好啦
