传送门

点双练习。

对于一张图，询问有多少条边不属于任意一个点双和多少条边至少属于两个点双。

显然，一张图里有多少个桥就是第一问的答案。

对于第二问，考虑对于一个点双，如果其中的边数等于点数，那么这个点双就是一个简单环，如果边数大于点数，那么这个点双里的所有边都至少属于两个点双。

证明的话画个图看看就好啦QAQ

//HDU 3394//by Cydiater//2016.11.2#include <iostream>#include <cstdlib>#include <cstdio>#include <queue>#include <map>#include <ctime>#include <cstring>#include <string>#include <algorithm>#include <iomanip>#include <bitset>#include <set>#include <cmath>#include <vector>using namespace std;#define ll long long#define up(i,j,n)		for(int i=j;i<=n;i++)#define down(i,j,n)		for(int i=j;i>=n;i--)#define cmax(a,b) 		a=max(a,b)#define cmin(a,b)		a=min(a,b)#define Auto(i,node)	for(int i=LINK[node];i;i=e[i].next)#define vci vector<int>const int MAXN=2e5+5;const int oo=0x3f3f3f3f;inline int read(){	char ch=getchar();int x=0,f=1;	while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}	while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}	return x*f;}int LINK[MAXN],len=0,dfn[MAXN],low[MAXN],stack[MAXN],top=0,dfs_clock=0,ans1,ans2,N,M,group[MAXN],group_num=0;struct edge{	int y,next;}e[MAXN];vci block;namespace solution{	void Clear(){		len=ans1=ans2=dfs_clock=top=group_num=0;		memset(LINK,0,sizeof(LINK));		memset(dfn,0,sizeof(dfn));		memset(low,0,sizeof(low));		memset(group,0,sizeof(group));	}	inline void insert(int x,int y){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;}	inline void Insert(int x,int y){insert(x,y);insert(y,x);}	void init(){		Clear();		N=read();M=read();		if(N==0)exit(0);		up(i,1,M){			int x=read(),y=read();			Insert(x,y);		}	}	void col(){		int siz=block.size(),cnt=0;		up(i,0,siz-1)Auto(j,block[i])if(group[e[j].y]==group_num)cnt++;		cnt>>=1;		if(cnt>siz)ans2+=cnt;	}	void tarjan(int node,int father){		dfn[node]=low[node]=++dfs_clock;stack[++top]=node;		Auto(i,node)if(!dfn[e[i].y]){			tarjan(e[i].y,node);cmin(low[node],low[e[i].y]);			if(low[e[i].y]>dfn[node])ans1++;			if(low[e[i].y]>=dfn[node]){				int tmp;block.clear();group_num++;				do{					tmp=stack[top--];					block.push_back(tmp);					group[tmp]=group_num;				}while(tmp!=e[i].y);				block.push_back(node);group[node]=group_num;				col();			}		}else if(e[i].y!=father) cmin(low[node],dfn[e[i].y]);	}	void slove(){		up(i,1,N)if(!dfn[i])tarjan(i,0);		printf("%d %d\n",ans1,ans2);	}}int main(){	//freopen("input.in","r",stdin);	using namespace solution;	while(1){		init();		slove();	}	return 0;}

HDU3394:Railway