这道题是这次考试最大的遗憾……
当时先做了第二第三道最难的两道题才做的这道题，还剩大概一个半小时的时间吧，脑子已经一片浆糊了，只能打一个dfs暴力上去，呵呵，拿了20分，好慷慨的出题人……这道题正解让我想到了单色三角形那道题，他们的打法都并不在乎图的形状，只在乎与每个点的连边（虽然这道题要判断是否联通，还是要建图）。
现在说正解，这道题当晚被说为是桥，然而呵呵，是欧拉路理论。我们大可把每条边拆成两个点，那么显然，每个点入度都是偶数，那么这个图就是一个欧拉图了。如果我们要去拆边，那我们也只能去拆链接同一个点的两条边，这样才会合法。但是由于本题有一个自环的限制，我们要把自环单独考虑，首先如果我们选择两个自环边，显然都成立，然后如果一个是自环边一个是普通边呢？自环自然好说，那么我们可以第一步先走那个普通边，问题又回到了初始的状态，也是可以直接转移的。
但是我们忽略了一种情况，即所有虫洞并不是任意两个都可以互相抵达的，为什么说是虫洞而不是点呢，因为如果有一个点没有任何边与他相连也是无影响的，所以我用了一个并查集去搞他，还是比较好打的，省事。当然dfs也行。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #define N 100005 9 using namespace std;10 int n,m;11 long long rd[N],sum,sum2,fa[N],rd2[N];12 long long ans;13 int find(int x)14 {15 if(fa[x]==x)return x;16 else return fa[x]=find(fa[x]);17 }18 void hb(int x,int y)19 {20 int a=find(x),b=find(y);21 fa[a]=b;22 }23 int main()24 {25 scanf("%d%d",&n,&m);26 for(int i=1;i<=n;i++) fa[i]=i;27 for(int i=1;i<=m;i++)28 {29 int x,y;30 scanf("%d%d",&x,&y);31 if(x!=y)32 {33 rd[x]++;34 rd[y]++;35 hb(x,y);36 }37 else38 {39 sum++;40 }41 rd2[x]++,rd2[y]++;42 }43 int bj=0;44 for(int i=1;i<=n;i++)45 {46 if(rd2[i]!=0)47 {48 find(i);49 bj=i;50 break;51 }52 }53 for(int i=1;i<=n;i++)54 {55 if(rd2[i]!=0&&find(i)!=fa[bj])56 {57 printf("0\n");58 exit(0);59 }60 }61 for(int i=1;i<=n;i++) ans+=(rd[i]-1)*rd[i]/2,sum2+=rd[i];62 ans+=sum*sum2/2;63 ans+=sum*(sum-1)/2;64 printf("%lld\n",ans);65 return 0;66 }