题目 : friend set
时间限制:5000ms
单点时限:1000ms
内存限制:256MB
描述现在存有大量一对好友的列表，好友的好友也是好友，所有有好友关系的形成一个圈子，请找出圈子中的人数。
输入第一行是N，表示好友对的数量(1<= N <= 100000)。之后N行每行是两个数字，代表玩家代号，用空格分隔。玩家代号是整数且<= 1000000000。输出将每个圈子中的人数按降序排列。
样例输入
8
1 2
2 3
5 4
3 4
6 7
8 6
9 10
10 11
样例输出
5
3
3
题目来自网易游戏笔试题
我自己的一个想法
图
这其实就是一个给定一个无向图,找出其联通分量的应用看代码
package graph;import java.util.ArrayList;import java.util.LinkedList;import prac.friendset2;public class FriendSet {private ArrayList<Object> vertexList;// 存储点的链表private int[][] edges;// 邻接矩阵，用来存储边private int numOfEdges;// 边的数目public FriendSet(int n) {// 初始化矩阵，一维数组，和边的数目edges = new int[n][n];vertexList = new ArrayList<Object>(n);numOfEdges = 0;}// 得到结点的个数public int getNumOfVertex() {return vertexList.size();}// 得到边的数目public int getNumOfEdges() {return numOfEdges;}// 返回结点i的数据public Object getValueByIndex(int i) {return vertexList.get(i);}// 插入结点public void insertVertex(Object vertex) {vertexList.add(vertexList.size(), vertex);}// 插入边public void insertEdge(int v1, int v2, int weight) {edges[v1][v2] = weight;numOfEdges++;}// 插入边public void insertEdge(int v1, int v2) {edges[v1][v2] = 1;edges[v2][v1] = 1;numOfEdges++;}// 得到第一个邻接结点的下标public int getFirstNeighbor(int index) {for (int j = 0; j < vertexList.size(); j++) {if (edges[index][j] > 0) {return j;}}return -1;}// 根据前一个邻接结点的下标来取得下一个邻接结点public int getNextNeighbor(int v1, int v2) {for (int j = v2 + 1; j < vertexList.size(); j++) {if (edges[v1][j] > 0) return j;}return -1;}// 私有函数，广度优先遍历private void broadFirstSearch(boolean[] isVisited, int i) {int u, w;int size=1;LinkedList<Integer> queue = new LinkedList<Integer>();// 访问结点iSystem.out.print(getValueByIndex(i) + " ");isVisited[i] = true;// 结点入队列queue.addLast(i);while (!queue.isEmpty()) {u = ((Integer) queue.removeFirst()).intValue();w = getFirstNeighbor(u); //u的第1个w节点while (w != -1) {//一个u 连接n个w if (!isVisited[w]) {size++;// 访问该结点System.out.print(getValueByIndex(w) + " ");// 标记已被访问isVisited[w] = true;// 入队列queue.addLast(w);}// 寻找下一个邻接结点w = getNextNeighbor(u, w);}}System.out.println("这个圈 共有 "+size+" 个人");} // 对外公开函数，广度优先遍历public void broadFirstSearch() {boolean[] isVisited = new boolean[getNumOfVertex()];int numOfVertex=getNumOfVertex();for (int i = 0; i < numOfVertex; i++) isVisited[i] = false;for (int i = 0; i < numOfVertex; i++) {if (!isVisited[i]) broadFirstSearch(isVisited, i);}}public static void main(String args[]) {FriendSet graph = getGraph();graph.broadFirstSearch();}private static FriendSet getGraph() {int n = 9, e = 9;// 分别代表结点个数和边的数目FriendSet graph = new FriendSet(15);for (int i=0;i<15;i++) {graph.insertVertex(i);// 插入结点}// 插入九条边graph.insertEdge(1, 2);graph.insertEdge(2, 3);graph.insertEdge(5, 4);graph.insertEdge(3, 4);graph.insertEdge(6, 7);graph.insertEdge(8, 6);graph.insertEdge(9, 10);graph.insertEdge(10, 11);return graph;}}
输出结果:
0 这个圈 共有 1 个人
1 2 3 4 5 这个圈 共有 5 个人
6 7 8 这个圈 共有 3 个人
9 10 11 这个圈 共有 3 个人
12 这个圈 共有 1 个人
13 这个圈 共有 1 个人
14 这个圈 共有 1 个人
和朋友聊天,他看了代码后说,用图来解决这种问题是很标准的
但是有点大材小用
确实,如果我给一个测试用例
1
5 2543545
是5号节点与2543545号节点是朋友
而且也只有这一个关系
请问,一共需要多少个节点?
似乎需要2个节点
问题是,2怎么来的?
我还得根据n条关系,找出最少需要几个节点!
Circle方法
朋友给出了这样一个想法用一个list<Relation> reliations装所有的关系
用一个list<Set<Integer>> circles 装所有的圈子(最开始的时候,圈子数为0)
循环遍历每一组关系
判断这组关系是否属于某一个circle(一组关系中的两个参数只要有一个在某个circle中,我们就说这个关系属于这个circle)
判断刚才的那组关系是否属于第二个circle,如果某一个关系同时属于两个circle 我们就把两个circle合并
如何某个关系不属于已知的任何一个circle 那么就新产生一个circle,并把这组关系里的两个值都放进这个新的circle中
遍历circles,输出每个circle的size即可
我觉得这个方法比图更精妙
看代码
package prac;/*** Created by zhangchen on /9/14.*/import java.util.*;/*** Created by zhangchen on /9/14.*/public class friendset2 {public static void main(String[] args) {// Scanner scanner = new Scanner(System.in);// int n = scanner.nextInt();// scanner.nextLine();// FriendShip[] friendShips = new FriendShip[n];// for (int i = 0; i < n; i++) {// friendShips[i] = new FriendShip();// friendShips[i].f1 = scanner.nextInt();// friendShips[i].f2 = scanner.nextInt();// }int n=8;FriendShip[] friendShips = new FriendShip[n];getData(friendShips);List<Set<Integer>> circles = new ArrayList<>();for (int i = 0; i < n; i++) {boolean flag = false;boolean more = false;int connectwith = -1;for (int j = 0; j < circles.size(); j++) {if (circles.get(j).contains(friendShips[i].f1)) {circles.get(j).add(friendShips[i].f2);if (connectwith >= 0 && connectwith != j) more = true;if (connectwith == -1) connectwith = j;flag = true;} else if (circles.get(j).contains(friendShips[i].f2)) {circles.get(j).add(friendShips[i].f1);if (connectwith >= 0 && connectwith != j) more = true;if (connectwith == -1) connectwith = j;flag = true;}if (more) {for (int e : circles.get(j)) {circles.get(connectwith).add(e);}circles.remove(j);}}if (!flag) {Set<Integer> circle = new HashSet<>();circle.add(friendShips[i].f1);circle.add(friendShips[i].f2);circles.add(circle);}}Collections.sort(circles, new Comparator<Set<Integer>>() {@Overridepublic int compare(Set<Integer> o1, Set<Integer> o2) {return o2.size() - o1.size();}});for (int k = 0; k < circles.size(); k++)System.out.println(circles.get(k).size());}private static void getData(FriendShip[] friendShips) {FriendShip friendShip = new FriendShip();friendShip.f1 = 1;friendShip.f2 = 2;friendShips[0] = friendShip;friendShip = new FriendShip();friendShip.f1 = 10;friendShip.f2 = 11;friendShips[1] = friendShip;friendShip = new FriendShip();friendShip.f1 = 4;friendShip.f2 = 5;friendShips[2] = friendShip;friendShip = new FriendShip();friendShip.f1 = 4;friendShip.f2 = 3;friendShips[3] = friendShip;friendShip = new FriendShip();friendShip.f1 = 6;friendShip.f2 = 7;friendShips[4] = friendShip;friendShip = new FriendShip();friendShip.f1 = 9;friendShip.f2 = 10;friendShips[5] = friendShip;friendShip = new FriendShip();friendShip.f1 = 3;friendShip.f2 = 2;friendShips[6] = friendShip;friendShip = new FriendShip();friendShip.f1 = 7;friendShip.f2 = 2;friendShips[7] = friendShip;}}class FriendShip {int f1;int f2;}
