首页 > 代码库 > HDU 3849 无向图的割边
HDU 3849 无向图的割边
By Recognizing These Guys, We Find Social Networks Useful
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 125536/65536 K (Java/Others)
Total Submission(s): 2319 Accepted Submission(s): 603
Problem Description
Social Network is popular these days.The Network helps us know about those guys who we are following intensely and makes us keep up our pace with the trend of modern times.
But how?
By what method can we know the infomation we wanna?In some websites,maybe Renren,based on social network,we mostly get the infomation by some relations with those "popular leaders".It seems that they know every lately news and are always online.They are alway publishing breaking news and by our relations with them we are informed of "almost everything".
(Aha,"almost everything",what an impulsive society!)
Now,it‘s time to know what our problem is.We want to know which are the key relations make us related with other ones in the social network.
Well,what is the so-called key relation?
It means if the relation is cancelled or does not exist anymore,we will permanently lose the relations with some guys in the social network.Apparently,we don‘t wanna lose relations with those guys.We must know which are these key relations so that we can maintain these relations better.
We will give you a relation description map and you should find the key relations in it.
We all know that the relation bewteen two guys is mutual,because this relation description map doesn‘t describe the relations in twitter or google+.For example,in the situation of this problem,if I know you,you know me,too.
But how?
By what method can we know the infomation we wanna?In some websites,maybe Renren,based on social network,we mostly get the infomation by some relations with those "popular leaders".It seems that they know every lately news and are always online.They are alway publishing breaking news and by our relations with them we are informed of "almost everything".
(Aha,"almost everything",what an impulsive society!)
Now,it‘s time to know what our problem is.We want to know which are the key relations make us related with other ones in the social network.
Well,what is the so-called key relation?
It means if the relation is cancelled or does not exist anymore,we will permanently lose the relations with some guys in the social network.Apparently,we don‘t wanna lose relations with those guys.We must know which are these key relations so that we can maintain these relations better.
We will give you a relation description map and you should find the key relations in it.
We all know that the relation bewteen two guys is mutual,because this relation description map doesn‘t describe the relations in twitter or google+.For example,in the situation of this problem,if I know you,you know me,too.
Input
The input is a relation description map.
In the first line,an integer t,represents the number of cases(t <= 5).
In the second line,an integer n,represents the number of guys(1 <= n <= 10000) and an integer m,represents the number of relations between those guys(0 <= m <= 100000).
From the second to the (m + 1)the line,in each line,there are two strings A and B(1 <= length[a],length[b] <= 15,assuming that only lowercase letters exist).
We guanrantee that in the relation description map,no one has relations with himself(herself),and there won‘t be identical relations(namely,if "aaa bbb" has already exists in one line,in the following lines,there won‘t be any more "aaa bbb" or "bbb aaa").
We won‘t guarantee that all these guys have relations with each other(no matter directly or indirectly),so of course,maybe there are no key relations in the relation description map.
In the first line,an integer t,represents the number of cases(t <= 5).
In the second line,an integer n,represents the number of guys(1 <= n <= 10000) and an integer m,represents the number of relations between those guys(0 <= m <= 100000).
From the second to the (m + 1)the line,in each line,there are two strings A and B(1 <= length[a],length[b] <= 15,assuming that only lowercase letters exist).
We guanrantee that in the relation description map,no one has relations with himself(herself),and there won‘t be identical relations(namely,if "aaa bbb" has already exists in one line,in the following lines,there won‘t be any more "aaa bbb" or "bbb aaa").
We won‘t guarantee that all these guys have relations with each other(no matter directly or indirectly),so of course,maybe there are no key relations in the relation description map.
Output
In the first line,output an integer n,represents the number of key relations in the relation description map.
From the second line to the (n + 1)th line,output these key relations according to the order and format of the input.
From the second line to the (n + 1)th line,output these key relations according to the order and format of the input.
Sample Input
1
4 4
saerdna aswmtjdsj
aswmtjdsj mabodx
mabodx biribiri
aswmtjdsj biribiri
Sample Output
1
saerdna aswmtjdsj
题目意思：
给你n，m表示一个图的n个点,m条边。 下面m行为 x ,y即x和y之间有条边，求割边，2个坑点：若图不连通输出0；若有多条割边按输入先后顺序输出，而且x，y顺序也和输入时一致 （好坑。。。）
思路：
求割边就不多说了，网上都有。发发牢骚。。。这道题在我last submit中一版多才AC。。题目中好像没说不连通输出0啊。。。表示很无语。。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <string> 4 #include <iostream> 5 #include <algorithm> 6 #include <vector> 7 #include <queue> 8 #include <stack> 9 #include <map> 10 using namespace std; 11 #define N 10005 12 13 struct node{ 14 int x, y, id, id1, id2; 15 }ans[N]; 16 17 struct mem{ 18 int y, id, id1, id2; 19 }; 20 21 vector<mem>ve[N]; 22 map<string,int>ma; 23 map<int,string>mb; 24 int low[N], dfn[N]; 25 int visited[N]; 26 int n, m, dfn_clock; 27 int nu; 28 29 void init(){ 30 for(int i=0;i<=n;i++) ve[i].clear(); 31 ma.clear();mb.clear(); 32 memset(dfn,-1,sizeof(dfn)); 33 memset(visited,0,sizeof(visited)); 34 } 35 36 void dfs(int u,int fa){ 37 int i, j, k, v; 38 node p; 39 mem q; 40 //printf("1111111111\n"); 41 low[u]=dfn[u]=dfn_clock++; 42 43 visited[u]=1; 44 for(i=0;i<ve[u].size();i++){ 45 q=ve[u][i]; 46 if(q.y==fa) continue; 47 // printf("%d\n",v); 48 if(!visited[q.y]){ 49 dfs(q.y,u); 50 low[u]=min(low[u],low[q.y]); 51 if(low[q.y]>dfn[u]) { 52 p.x=u;p.y=q.y;p.id=q.id;p.id1=q.id1;p.id2=q.id2; 53 ans[nu++]=p; 54 } 55 } 56 else low[u]=min(low[u],dfn[q.y]); 57 58 } 59 } 60 61 bool cmp(node a,node b){ 62 return a.id<b.id; 63 } 64 65 main() 66 { 67 int t, i, j, k, id; 68 char s1[200], s2[200]; 69 mem p; 70 cin>>t; 71 while(t--){ 72 scanf("%d %d",&n,&m); 73 init();k=1;id=1; 74 while(m--){ 75 scanf("%s%s",s1,s2); 76 if(ma[s1]==0) ma[s1]=k,mb[k]=s1,++k; 77 if(ma[s2]==0) ma[s2]=k,mb[k]=s2,++k; 78 int x=ma[s1], y=ma[s2]; 79 p.y=ma[s2];p.id=id++;p.id1=1;p.id2=2; 80 ve[x].push_back(p); 81 p.y=ma[s1];p.id=id++;p.id1=2;p.id2=1; 82 ve[y].push_back(p); 83 } 84 85 dfn_clock=nu=0; 86 dfs(1,-1); 87 int f=1; 88 for(i=1;i<=n;i++) { 89 if(dfn[i]==-1){ 90 break; 91 } 92 } 93 if(i<=n){ 94 printf("0\n");continue; 95 } 96 sort(ans,ans+nu,cmp); 97 printf("%d\n",nu); 98 for(i=0;i<nu;i++){ 99 if(ans[i].id1<ans[i].id2)100 cout<<mb[ans[i].x]<<" "<<mb[ans[i].y]<<endl;101 else cout<<mb[ans[i].y]<<" "<<mb[ans[i].x]<<endl;102 }103 }104 }
HDU 3849 无向图的割边
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。