首页 > 代码库 > hdu3849-By Recognizing These Guys, We Find Social Networks Useful：双连通分量
hdu3849-By Recognizing These Guys, We Find Social Networks Useful：双连通分量
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): 2354 Accepted Submission(s): 613
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
1saerdna aswmtjdsj
Source
2011 Invitational Contest Host by BUPT
题意：有n个人名和m条边（用人名来表示），求出这个图中的所有桥（以人名表示边来输出）。
算法：用map来hash，边(a,b)的hash值为a*10000+b，然后求桥，最后按输入顺序遍历一遍所有边，如果为桥的话就输出。
此题有一个坑就是当图不连通的时候直接输出0就可以了。
1 #include <iostream> 2 #include <stdio.h> 3 #include <map> 4 #include <memory.h> 5 #include <vector> 6 using namespace std; 7 8 9 const int maxn = 10000 + 10; 10 int low[maxn],pre[maxn],dfs_clock=0; 11 map<int,bool> isbridge; 12 vector<int> G[maxn]; 13 int cnt_bridge; 14 int father[maxn]; 15 16 int getid(int u,int v) 17 { 18 return u*10000+v; 19 } 20 21 int dfs(int u, int fa) 22 { 23 father[u]=fa; 24 int lowu = pre[u] = ++dfs_clock; 25 int child = 0; 26 for(int i = 0; i < G[u].size(); i++) 27 { 28 int v = G[u][i]; 29 if(!pre[v]) // 没有访问过v 30 { 31 child++; 32 int lowv = dfs(v, u); 33 lowu = min(lowu, lowv); // 用后代的low函数更新自己 34 if(lowv > pre[u]) // 判断边(u,v)是否为桥 35 { 36 isbridge[getid(u,v)]=isbridge[getid(v,u)]=true; 37 cnt_bridge++; 38 } 39 } 40 else if(pre[v] < pre[u] && v != fa) 41 { 42 lowu = min(lowu, pre[v]); // 用反向边更新自己 43 } 44 } 45 return low[u]=lowu; 46 } 47 48 void init(int n) 49 { 50 isbridge.clear(); 51 memset(pre,0,sizeof pre); 52 cnt_bridge=dfs_clock=0; 53 for(int i=0; i<n; i++) 54 { 55 G[i].clear(); 56 } 57 } 58 59 60 bool vis[maxn]; 61 int cnt; 62 int dfs_conn(int u) 63 { 64 vis[u]=true; 65 cnt++; 66 for(int i=0;i<G[u].size();i++) 67 { 68 int v=G[u][i]; 69 if(!vis[v]) 70 dfs_conn(v); 71 } 72 } 73 74 bool isconn(int n) 75 { 76 memset(vis,false,sizeof vis); 77 cnt=0; 78 dfs_conn(0); 79 return cnt==n; 80 } 81 82 83 int main() 84 { 85 #ifndef ONLINE_JUDGE 86 freopen("in.txt","r",stdin); 87 #endif 88 89 int T; 90 cin>>T; 91 while(T--) 92 { 93 map<string,int> id; 94 map<int,string> id2; 95 vector<int> edges; 96 int n,m; 97 scanf("%d %d",&n,&m); 98 init(n); 99 int num=0;100 for(int i=0;i<m;i++)101 {102 103 char str1[20],str2[20];104 scanf("%s %s",str1,str2);105 int a,b;106 if(id.count((string)str1)>0)107 {108 a=id[(string)str1];109 }110 else111 {112 a=id[(string)str1]=num++;113 }114 115 if(id.count((string)str2)>0)116 {117 b=id[(string)str2];118 }119 else120 {121 b=id[(string)str2]=num++;122 }123 124 id2[a]=(string)str1;125 id2[b]=(string)str2;126 127 G[a].push_back(b);128 G[b].push_back(a);129 edges.push_back(getid(a,b));130 }131 132 if(!isconn(n))133 {134 puts("0");135 continue;136 }137 138 dfs(0,-1);139 cout<<cnt_bridge<<endl;140 for(int i=0;i<edges.size();i++)141 {142 if(isbridge[edges[i]])143 {144 printf("%s %s\n",id2[edges[i]/10000].c_str(),id2[edges[i]%10000].c_str());145 }146 }147 }148 149 return 0;150 }
hdu3849-By Recognizing These Guys, We Find Social Networks Useful：双连通分量
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。