HDU 3394 Railway（tarjan求桥的个数和点双连通图）

看了快两天才基本把这题搞明白
图论概念太多了 头疼得很
题解都看了好久才弄明白
交的时候g++就莫名其妙的t了
c++就能过 就很迷惑

题目思路

容易看出题目所说的不必要的点就是桥
而冲突的边我们可以求点双连通图
如果某个点双连通图中边数量大于点数量
那么这个图就构成了多个环
而该图上所有的边也就是冲突的边
我们用tarjan算法求桥和割点
每次得到割点时我们同时也得到了一个点双连通图
将该连通图出栈并记录连通图中的点
最后记录单向边的数量 与点的数量进行比较

ac代码

#include <stdio.h>#include <iostream>#include <algorithm>#include <math.h>#include <string.h>#include <vector>#include <stack>#include <queue>#include <map>#include <set>#include <utility>#define pi 3.1415926535898#define ll long long#define lson rt<<1#define rson rt<<1|1#define eps 1e-6#define ms(a,b) memset(a,b,sizeof(a))#define legal(a,b) a&b#define print1 printf(\"111\\n\")using namespace std;const int maxn = 2e5+10;const int inf = 0x3f3f3f3f;const ll llinf =0x3f3f3f3f3f3f3f3f;const int mod = 1e9+7;struct node{int to,next;}e[maxn];int n,m,len,first[maxn];int ans1,ans2,index,block,top;//以下数组分别记录点的可回溯的最小序号，点入栈的序号，栈内元素序号，某点属于的连通图，某点是否在栈中int low[maxn],dfn[maxn],st[maxn],belong[maxn],ins[maxn];//记录该点是否在点双连通图中int flag[maxn];vector<int>vec;void add(int u,int v)//链式前向星建图{e[len].to=v;e[len].next=first[u];first[u]=len++;}void init(){len=0;ms(first,-1);ms(dfn,0);ms(ins,0);ans1=ans2=index=block=top=0;}void counts()//计算单向边的个数{ms(flag,0);for(int i=0;i<vec.size();i++) flag[vec[i]]=1;int tem=0;for(int i=0;i<vec.size();i++){int u=vec[i];for(int j=first[u];~j;j=e[j].next){if(flag[e[j].to])tem++;}}tem/=2;//因为我们建图建的是双向图 所以求单向边时要除2if(tem>vec.size())ans2+=tem;//边数量大于点数量时 连通图中边都是冲突边}void tarjan(int u,int fa){int v;low[u]=dfn[u]=++index;//标记序号st[top++]=u;//进栈ins[u]=1;//标记进栈for(int i=first[u];~i;i=e[i].next){v=e[i].to;if(v==fa)continue;if(!dfn[v])//如果未遍历则对该点进行操作{tarjan(v,u);low[u]=min(low[u],low[v]);//更新low值if(low[v]>dfn[u])ans1++;//记录桥的数量if(low[v]>=dfn[u])//割点满足的条件{vec.clear();//初始化block++;int tem;do{tem=st[--top];belong[tem]=block;vec.push_back(tem);ins[tem]=0;}while(tem!=v);//将该点双连通图每个点出栈并记录belong[u]=block;vec.push_back(u);counts();//计算冲突边数量}}else if(ins[v]){low[u]=min(low[u],dfn[v]);//点已在栈中 就更新low值}}}int main(){while(~scanf(\"%d%d\",&n,&m)&&n+m){init();for(int i=1;i<=m;i++){int x,y;scanf(\"%d%d\",&x,&y);x++,y++;add(x,y);add(y,x);}for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i,-1);printf(\"%d %d\\n\",ans1,ans2);}}