
回答 2 已采纳 Problem Description
Everyone knows how to calculate the shortest path in a directed graph. In fact, the opposite problem is also easy. Given the length of shortest path between each pair of vertexes, can you find the original graph?
Input
The first line is the test case number T (T ≤ 100).
First line of each case is an integer N (1 ≤ N ≤ 100), the number of vertexes.
Following N lines each contains N integers. All these integers are less than 1000000.
The jth integer of ith line is the shortest path from vertex i to j.
The ith element of ith line is always 0. Other elements are all positive.
Output
For each case, you should output “Case k: ” first, where k indicates the case number and counts from one. Then one integer, the minimum possible edge number in original graph. Output “impossible” if such graph doesn't exist.
Sample Input
3
3
0 1 1
1 0 1
1 1 0
3
0 1 3
4 0 2
7 3 0
3
0 1 4
1 0 2
4 2 0
Sample Output
Case 1: 6
Case 2: 4
Case 3: impossible

回答 1 已采纳 Let there be a simple graph with N vertices but we just know the degree of each vertex. Is it possible to reconstruct the graph only by these information?
A simple graph is an undirected graph that has no loops (edges connected at both ends to the same vertex) and no more than one edge between any two different vertices. The degree of a vertex is the number of edges that connect to it.
Input
There are multiple cases. Each case contains two lines. The first line contains one integer N (2 ≤ N ≤ 100), the number of vertices in the graph. The second line conrains N integers in which the ith item is the degree of ith vertex and each degree is between 0 and N1(inclusive).
Output
If the graph can be uniquely determined by the vertex degree information, output "UNIQUE" in the first line. Then output the graph.
If there are two or more different graphs can induce the same degree for all vertices, output "MULTIPLE" in the first line. Then output two different graphs in the following lines to proof.
If the vertex degree sequence cannot deduced any graph, just output "IMPOSSIBLE".
The output format of graph is as follows:
N E
u1 u2 ... uE
v1 v2 ... vE
Where N is the number of vertices and E is the number of edges, and {ui,vi} is the ith edge the the graph. The order of edges and the order of vertices in the edge representation is not important since we would use special judge to verify your answer. The number of each vertex is labeled from 1 to N. See sample output for more detail.
Sample Input
1
0
6
5 5 5 4 4 3
6
5 4 4 4 4 3
6
3 4 3 1 2 0
Sample Output
UNIQUE
1 0
UNIQUE
6 13
3 3 3 3 3 2 2 2 2 1 1 1 5
2 1 5 4 6 1 5 4 6 5 4 6 4
MULTIPLE
6 12
1 1 1 1 1 5 5 5 6 6 2 2
5 4 3 2 6 4 3 2 4 3 4 3
6 12
1 1 1 1 1 5 5 5 6 6 3 3
5 4 3 2 6 4 3 2 4 2 4 2
IMPOSSIBLE

回答 1 已采纳 Many of you know bipartite graph, which is an undirected graph whose vertices can be divided into two nonempty disjoint sets U and V such that every edge connnects a vertex in U to one in V, that is, there is no edge that connects a vertex v to another vertex which is in the same set of v. Similarly, a tripartite graph (which is also called Kengdie graph) is an undirected graph whose vertices can be divided into three nonempty disjoint sets U, V and W such that there is no edge that connects a vertex v to another vertex which is in the same set of v. A simple graph is a graph that has no loops and no more than one edge between any two different vertices. A graph is a simple tripartite graph if it is simple and it is a tripartite graph.
You are given two integers V and E, and are asked to construct a simple tripartite graph which has exactly V vertices and E edges. In these E edges, M of them are given to you. Besides, any two of the three disjoint vertices sets must have different sizes.
Input
The first line is the number of cases T (T <= 100). For each case, the first line gives three integers V, E and M (1 <= V <= 50, 1,000 <= E <= 1,000,000, 0 <= M <= min(E, 10,000)). Then M lines follow, each gives an edge V1 V2 (1 <= V1 V2 <= V), means there should be an edge between V1 and V2.
Output
For each case, output E lines, that are the edges of the graph you construct. If there are multiple solutions, output any one. If there is no such graph, do not output anything.
Sample Input
1
1 1000000 0
Sample Output

回答 1 已采纳 Description
Consider the following game on an undirected graph G. There are two players, a red color player R and a blue color player B. Initially all edges of G are uncolored. The two players alternately color an uncolored edge of G with their color until all edges are colored. The goal of B is that in the end, the bluecolored edges form a connected spanning subgraph of G. A connected spanning subgraph of G is a connected subgraph that contains all the vertexes of graph G. The goal of R is to prevent B from achieving his goal.
Assume that R starts the game. Suppose that both players play in the smartest way. Your task is to find out whether B will win the game.
Input
The input contains several test cases, ended by a line of `1 1'.
Each test case begins with a line of two integers n (1 <= n <= 10) and m (0 <= m <= 30), indicating the number of vertexes and edges in the graph. All vertexes are numbered from 0 to n  1.
Then m lines follow. Each line contains two integers p and q (0 <= p, q < n), indicating there is an edge between vertex p and vertex q.
It is possible that the graph contains more than one edge between two vertexes and selfloops.
Output
For each test case print a line which is either 'YES' or 'NO' indicating B will win the game or not.
Sample Input
3 4
0 1
1 2
2 0
0 2
4 6
1 0
1 2
2 0
0 2
3 0
1 0
1 1
Sample Output
YES
NO

回答 2 已采纳 Description
An undirected graph is a set V of vertices and a set of E∈{V*V} edges.An undirected graph is connected if and only if for every pair (u,v) of vertices,u is reachable from v.
You are to write a program that tries to calculate the number of different connected undirected graph with n vertices.
For example,there are 4 different connected undirected graphs with 3 vertices.
![](http://poj.org/images/1737_1.jpg)
Input
The input contains several test cases. Each test case contains an integer n, denoting the number of vertices. You may assume that 1<=n<=50. The last test case is followed by one zero.
Output
For each test case output the answer on a single line.
Sample Input
1
2
3
4
0
Sample Output
1
1
4
38

回答 1 已采纳 Description
Let us consider an undirected graph G = . Let us denote by N(v) the set of vertices connected to vertex v (i.e. the set of neighbours of v). Recall that the number of vertices connected to v is called the degree of this vertex and is denoted by deg v.
We will call graph G strange if it is connected and for its every vertex v the following conditions are satisfied:
1. deg v >= 2 (i.e. there are at least two vertices connected to v)
2. If deg v = 2 then the two neighbours of v are not connected by an edge
3. If degv > 2 then there is u ∈ N(v), such that the following is true:
(a) deg u = 2
(b) Any two different vertices w1,w2 ∈ N(v) \ {u} are connected, i.e. (w1,w2) ∈ E.
You are given some strange graph G. Find hamiltonian cycle in it, i.e. find such cycle that it goes through every vertex of G exactly once.
Input
The first line of the input file contains two integer numbers N and M  the number of vertices and edges in G respectively (3 <= N <= 10 000, M <= 100 000). 2M integer numbers follow  each pair represents vertices connected by the corresponding edge (vertices are numbered from 1 to N). It is guaranteed that each edge occurs exactly once in the input file and that there are no loops (i.e. ends of each edge are distinct).
Output
If there is no hamiltonian cycle in G, print 1 on the first line of the output file. In the other case output N numbers  the sequence of vertices of G as they appear in the hamiltonian cycle found (note that the last vertex must be connected to the first one). If there are several solutions, output any one.
Sample Input
4 4
1 2 2 3 3 4 4 1
Sample Output
1 2 3 4

回答 2 已采纳 Problem Description As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:
There is an undirected graph with n vertices and m edges. Then Yuta does q operations on this graph. Each operation is described by two integers L,R (1≤L≤R≤n) and can be split into three steps:
1. Delete all the edges which have at least one vertice outside the range [L,R].
2. Yuta wants you to tell him the number of connected component of the graph.
3. Restore the graph.
This task is too hard for Rikka to solve. Can you help her?
Input There are at most 100 testcases and there are at least 97 testcases with n,m,q≤1000.
For each testcase, the first line contains three numbers n,m,q (n,q≤105,m≤2×105).
Then m lines follow. Each line contains two numbers ui,vi (1≤ui,vi≤105) which describe an edge of the graph.
Then q lines follows. Each line contains two numbers Li,Ri (1≤L≤R≤n) which describe an operation.
Output For each operation you need print a single line with a single number  the answer of this operation.
Sample Input
3 3 2
1 2
1 3
2 3
1 2
1 3
Sample Output
2
1

回答 1 已采纳 Description
Alice and Bob play the following game. First, Alice draws some directed graph with N vertices and M arcs. After that Bob tries to destroy it. In a move he may take any vertex of the graph and remove either all arcs incoming into this vertex, or all arcs outgoing from this vertex.
Alice assigns two costs to each vertex: Wi+ and Wi. If Bob removes all arcs incoming into the ith vertex he pays Wi+ dollars to Alice, and if he removes outgoing arcs he pays Wi dollars.
Find out what minimal sum Bob needs to remove all arcs from the graph.
Input
Input file describes the graph Alice has drawn. The first line of the input file contains N and M (1 <= N <= 100, 1 <= M <= 5000). The second line contains N integer numbers specifying Wi+. The third line defines Wi in a similar way. All costs are positive and do not exceed 106 . Each of the following M lines contains two integers describing the corresponding arc of the graph. Graph may contain loops and parallel arcs.
Output
On the first line of the output file print W  the minimal sum Bob must have to remove all arcs from the graph. On the second line print K  the number of moves Bob needs to do it. After that print K lines that describe Bob's moves. Each line must first contain the number of the vertex and then '+' or '' character, separated by one space. Character '+' means that Bob removes all arcs incoming into the specified vertex and '' that Bob removes all arcs outgoing from the specified vertex.
Sample Input
3 6
1 2 3
4 2 1
1 2
1 1
3 2
1 2
3 1
2 3
Sample Output
5
3
1 +
2 
2 +

回答 1 已采纳 There was no edge connecting one vertex and the vertex itself. There was no two edges connecting the same pair of vertices. It is special because the each vertex is connected to at most two black edges and at most two white edges.
One day, the demon broke this graph by copying all the vertices and in one copy of the graph, the demon only keeps all the black edges, and in the other copy of the graph, the demon keeps all the white edges. Now people only knows there are w0 vertices which are connected with no white edges, w1 vertices which are connected with 1 white edges, w2 vertices which are connected with 2 white edges, b0 vertices which are connected with no black edges, b1 vertices which are connected with 1 black edges and b2 vertices which are connected with 2 black edges.
The precious graph should be fixed to guide people, so some people started to fix it. If multiple initial states satisfy the restriction described above, print any of them.
Input
The first line of the input is a single integer T (T≤700), indicating the number of testcases.
Each of the following T lines contains w0,w1,w2,b0,b1,b2. It is guaranteed that 1≤w0,w1,w2,b0,b1,b2≤2000 and b0+b1+b2=w0+w1+w2.
It is also guaranteed that the sum of all the numbers in the input file is less than 300000.
Output
For each testcase, if there is no available solution, print −1. Otherwise, print m in the first line, indicating the total number of edges. Each of the next m lines contains three integers x,y,t, which means there is an edge colored t connecting vertices x and y. t=0 means this edge white, and t=1 means this edge is black. Please be aware that this graph has no selfloop and no multiple edges. Please make sure that 1≤x,y≤b0+b1+b2.
Sample Input
2
1 1 1 1 1 1
1 2 2 1 2 2
Sample Output
1
6
1 5 0
4 5 0
2 4 0
1 4 1
1 3 1
2 3 1

jzwei023的博客 Graph Embedding 算法主要经历了以下三代的发展： 第一代：基于矩阵特征向量（MDS、LLE） 第二代：基于Random Walk（Deep Walk 、Node2Vec） 第二代：基于Deep Learning（SDNE、GCN、GraphSAGE） Deep walk 主要... 
召唤师的峡谷的博客 文章目录GraphEmbedding系列总结Word2VecItem2VecDeepWalkLINENode2VecSDNEStruc2VecEGES参考文献 GraphEmbedding系列总结 Embedding从入门到专家必读的十篇论文 深度学习中不得不学的Graph Embedding方法 Graph ... 
SteinwayCaiZhuo的博客 Graph Embedding指把graph转化为低维vector，使得Graph上的问题可以用vector上的方法处理。 这样做的意义在于： 低维vector形式的算法相比原graph形式的算法所需算力更小 低维vector形式的算法更多更强 我从一篇... 
RecDay2018的博客 图（Graph）是一个常见的数据结构，现实世界中有很多很多任务可以抽象成图问题，比如社交网络，蛋白体结构，交通路网数据，以及很火的知识图谱等，甚至规则网络结构数据（如图像，视频等）也是图数据的一种特殊形式... 
dili8870的博客 而基于knowledge graph生成的物品向量可以被称为补充信息（side information）embedding向量，当然，根据补充信息类别的不同，可以有多个side information embedding向量。 **那么如何融合一个物品的多个embedding... 
一枚石头的博客 3.pycharm自动为graph embedding项目创建一个虚拟环境 关于python使用虚拟环境的好处 方便对项目进行包管理 4.根据graph embedding的提示，配置环境 首先安装tensorflow pip install tensorflow 可以看到安装的是... 
稷殿下的博客 Why do we need graph embedding Machine learning algorithms are tuned for continuous data, hence why embedding is always to a continuous vector space. What is graph embedding Definition Graph ... 
看穿数据之美的博客 文章目录介绍框架基于用户历史行为的 Item Graph的构建基本的Graph Embedding使用辅助信息的Graph Embedding使用辅助信息的增强型Graph Embedding实验离线评估在线A/B测Case Study系统部署和操作总结和未来展望 ... 
qq_906638174的博客 网络嵌入与图嵌入在目标和假设上具有实质性的差异。网络嵌入有两个目标：重建原始网络和支持网络推断。图嵌入的目标主要为图重建。图嵌入可以看作是网络嵌入的一种特例。此外，图嵌入算法经常作用在特征表示数据集所... 
玛卡巴卡米卡巴卡的博客 Graph Embedding Techniques, Applications, and Performance: A Survey Representation Learning on Graphs: Methods and Applications A Comprehensive Survey of Graph Embedding:Problems,Techniques and... 
山幺幺的博客 想看原文戳这里 1. introduction ...A KG is a multirelational graph composed of entities (nodes) and relations (different types of edges). (2) examples Freebase, DBpedia, YAGO, NELL...