| C电压 | ||
|
第一行两个空格分隔的正整数N和M，表示电路中有N个节点和M根电阻。
接下来M行，第i行有两个空格分隔的正整数Ai和Bi(1<=Ai<=N,1<=Bi<=N,Ai≠Bi)，表示第i个电阻连接节点Ai和节点Bi。
输出一行一个整数，代表电路维护时可选择的使其不流的电阻个数。
4 4
1 2
2 3
3 2
4 3
2
这道题与二分图有关，我们要使得去掉一条边后使得电路图成为一个标准的二分图
所以我们用dfs搜一遍，然后找到一条被所有的奇数边包括并且不被所有的偶数边包括的边 并且找出这样的边的个数即可
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,ans,f,i,cnt=1;
int he[100010],de[100010],color[(100010)<<2],to[(100010)<<2],ne[(100010)<<2],a[100010],aa[100010];
void add(int x,int y)
{
cnt++;
to[cnt]=y;
ne[cnt]=he[x];
he[x]=cnt;
}//建树
void dfs(int x)
{
for(int i=he[x];i;i=ne[i])
{
if(de[to[i]]==-1)de[to[i]]=de[x]+1,color[i]=color[i^1]=1,dfs(to[i]);
}
}
void find(int x)
{
for(int i=he[x];i;i=ne[i])
{
if(color[i]&&de[to[i]]>de[x])find(to[i]),a[x]+=a[to[i]],aa[x]+=aa[to[i]];
}
if(de[x]&&a[x]==f&&!aa[x])ans++;//满足两个条件
}
int main()
{
scanf("%d%d",&n,&m);
//cin>>n>>m;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);//无向图
}
memset(de,-1,sizeof(de));
for(int i=1;i<=n;i++)if(de[i]==-1)de[i]=0,dfs(i);//搜索
for(int j=1;j<=n;j++)
{
for(i=he[j];i;i=ne[i])
{
if(!color[i]&&de[to[i]]<de[j]){
if((de[j]-de[to[i]])&1)aa[j]++,aa[to[i]]--;
else f++,a[j]++,a[to[i]]--;
}
}
}
if(f==1)ans++;
for(int i=1;i<=n;i++)if(!de[i])find(i);
//cout<<ans;
printf("%d",ans);
}
原文：https://www.cnblogs.com/cocacolalala/p/11377489.html