朋友圈转发信息
描述:
在一个社交应用中，两个用户设定朋友关系后，则可以互相收到对方发布或转发的信息。当一个用户发布或转发一条信息时，他的所有朋友都能收到该信息。
现给定一组用户，及用户之间的朋友关系。
问：当某用户发布一条信息之后，为了让每个人都能在最早时间收到这条信息，这条信息最少需要被转发几次？
假设：对所有用户而言：
例如：
黄色节点表示转发用户，，蓝色数字为用户收到信息的时间。
运行时间限制:无限制
内存限制:无限制
输入:
Sender
[消息创建者编号]
Relationship
[朋友关系列表，1,2表示1和2是朋友关系]
End
如下：
Sender1Relationship1,21,31,42,52,63,64,64,75,65,85,96,76,86,97,910,7End
输出:
当某用户发布一条信息之后，为了让每个人都能在最早时间收到这条信息，这条信息最少需要被转发的次数
样例输入:Sender1Relationship1,21,31,42,52,63,64,64,75,65,85,96,76,86,97,910,7End
样例输出:4
import java.util.ArrayList;import java.util.Collection;import java.util.Collections;import java.util.Comparator;import java.util.HashSet;import java.util.Iterator;import java.util.List;import java.util.Scanner;import java.util.Set;public class Main {public static void main(String[] args) {// TODO Auto-generated method stubScanner cin = new Scanner(System.in);String line;int root;line = cin.nextLine();line = cin.nextLine();root = Integer.parseInt(line);List<node> all = new ArrayList<node>();node first = new node(root);all.add(first);line = cin.nextLine();while (cin.hasNext()){line = cin.nextLine();if(line.trim().equals("End"))break;String[] tmp = line.split(",");int index=-1;node t1=new node(Integer.parseInt(tmp[0])),t2=new node(Integer.parseInt(tmp[1]));index = all.indexOf(t1);if(-1 != index){t1 = all.get(index);}elseall.add(t1);index = all.indexOf(t2);if(-1 != index){t2 = all.get(index);}elseall.add(t2);t1.friends.add(t2);t2.friends.add(t1);}int count=0;Set<node> rr = new HashSet<node>();rr.add(first);first.r = true;Set<node> sender = new HashSet<>();Set<node> receive = new HashSet<>();sender.add(first);while(!yanzheng(all)){count += sendMsg(sender, receive);//copyMsg(receive, all);sender.clear();sender.addAll(receive);receive.clear();}System.out.println(count-1);}private static void copyMsg(Set<node> receive, List<node> all) {// TODO Auto-generated method stubIterator<node> it = receive.iterator();while(it.hasNext()){node x = it.next();all.get(all.indexOf(x)).r = true;}}private static int sendMsg(Set<node> sender, Set<node> receive) {// TODO Auto-generated method stubSet<node> friends ;int max = 0,count=0,c=0;node maxNode = null;for(node x:sender){friends = x.friends;for(node xx:friends){if(!xx.r){receive.add(xx);}}}while(!yanzheng(receive)){max = 0;for(node x:sender){c=0;friends = x.friends;for(node xx:friends){if(!xx.r){c++;}}if(c>max){max = c;maxNode = x;}}if(maxNode!=null){maxNode.sendMsg();count++;}}return count;}public static boolean yanzheng(Collection<node> all){boolean result = true;Iterator<node> its = all.iterator();while(its.hasNext())if(!its.next().r){result=false;break;}return result;}}class node{int num;boolean r = false;public node(int num) {super();this.num = num;}Set<node> friends = new HashSet<node>();public void sendMsg(){for(node x:friends){if(!x.r)x.r = true;}}public int findNew(){int c=0;for(node x:friends){if(!x.r)c++;}return c;}@Overridepublic boolean equals(Object obj) {// TODO Auto-generated method stubnode tmp = (node) obj;if(this.num == tmp.num)return true;elsereturn false;}@Overridepublic String toString() {// TODO Auto-generated method stubreturn String.valueOf(this.num);}}
因为有梦，所以勇敢出发，选择出发，便只顾风雨兼程。
