首页 > 代码库 > hdu3849 By Recognizing These Guys, We Find Social Networks Useful
hdu3849 By Recognizing These Guys, We Find Social Networks Useful
无向图求桥边数量,按照题目输入顺序输出桥边。
注意存的brig和边的对应关系。
#include <iostream> #include <cstdlib> #include <cstring> #include <string> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <map> #define inf 0x3f3f3f3f #pragma comment(linker, "/STACK:16777216") #define eps 1e-6 #define ll long long using namespace std; #define M 200003 #define N 10003 int head[N],num,dfn[N],low[N],n,m,idx,brig[M<<1],bum; struct edge { int st,ed,next; }E[M<<1]; void addedge(int x,int y) { E[num].st=x; E[num].ed=y; E[num].next=head[x]; head[x]=num++; } void tarjan(int u,int father) { int i,v; low[u]=dfn[u]=idx++; for(i=head[u];i!=-1;i=E[i].next) { v=E[i].ed; if(v==father)continue; if(dfn[v]==-1) { tarjan(v,u); low[u]=low[u]>low[v]?low[v]:low[u]; if(low[v]>dfn[u])//存第bum个桥对应边的编号 brig[bum++]=i; } else low[u]=low[u]>dfn[v]?dfn[v]:low[u]; } } void init() { memset(dfn,-1,sizeof dfn); memset(head,-1,sizeof head); num=bum=idx=0; } string hash[N]; string s1,s2; bool cmp(int a,int b) { return a<b; } int main() { int icy,i,cnt; scanf("%d",&icy); while(icy--) { scanf("%d%d",&n,&m); init(); map<string,int> mp; cnt=1; for(i=0;i<m;i++) { cin>>s1>>s2; if(!mp[s1]) hash[cnt]=s1,mp[s1]=cnt++; if(!mp[s2]) hash[cnt]=s2,mp[s2]=cnt++; addedge(mp[s1],mp[s2]); addedge(mp[s2],mp[s1]); } tarjan(1,-1); for(i=1;i<=n;i++)//判断图不联通 if(dfn[i]==-1) break; if(i<=n) { printf("0\n"); continue; } printf("%d\n",bum); sort(brig,brig+bum,cmp); for(int j=0;j<bum;j++) { i=brig[j]; if(i&1) i--; cout<<hash[E[i].st]<<' '<<hash[E[i].ed]<<endl; } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。