程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> CSU 1659: Graph Center(SPFA)

CSU 1659: Graph Center(SPFA)

編輯:C++入門知識

CSU 1659: Graph Center(SPFA)


1659: Graph Center

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 63 Solved: 25
[Submit][Status][Web Board]

Description

The center of a graph is the set of all vertices of minimum eccentricity, that is, the set of all vertices A where the greatest distance d(A,B) to other vertices B is minimal. Equivalently, it is the set of vertices with eccentricity equal to the graph's radius. Thus vertices in the center (central points) minimize the maximal distance from other points in the graph.
------wikipedia
Now you are given a graph, tell me the vertices which are the graph center.

Input

There are multiple test cases.
The first line will contain a positive integer T (T ≤ 300) meaning the number of test cases.
For each test case, the first line contains the number of vertices N (3 ≤ N ≤ 100) and the number of edges M (N - 1 ≤ N * (N - 1) / 2). Each of the following N lines contains two vertices x (1 ≤ x ≤ N) and y (1 ≤ y ≤ N), meaning there is an edge between x and y.

Output

The first line show contain the number of vertices which are the graph center. Then the next line should list them by increasing order, and every two adjacent number should be separated by a single space.

Sample Input

2
4 3
1 3
1 2
2 4
5 5
1 4
1 3
2 4
2 3
4 5

Sample Output

2
1 2
3
1 2 4

HINT

 

Source

#include 
#include 
#include 
using namespace std; 
  
const int MAXN = 105; 
const int MAXM = 100005; 
const int INF = 1<<30; 
struct EDG{ 
    int to,next; 
}edg[MAXM]; 
int eid,head[MAXN]; 
  
void init(){ 
    eid=0; 
    memset(head,-1,sizeof(head)); 
} 
void addEdg(int u,int v){ 
    edg[eid].to=v; edg[eid].next=head[u]; head[u]=eid++; 
    edg[eid].to=u; edg[eid].next=head[v]; head[v]=eid++; 
} 
int spfa(int s,int n){ 
    queueq; 
    bool inq[MAXN]={0}; 
    int d[MAXN]; 
    for(int i=1; i<=n; i++) 
        d[i]=INF; 
    d[s]=0; 
    q.push(s); 
    while(!q.empty()){ 
        int u=q.front(); q.pop(); 
        inq[s]=0; 
        for(int i=head[u]; i!=-1; i=edg[i].next){ 
            int v=edg[i].to; 
            if(d[v]>d[u]+1){ 
                d[v]=d[u]+1; 
                if(!inq[v]) 
                 q.push(v),inq[v]=1; 
            } 
        } 
    } 
    int maxt=0; 
    for(int i=1; i<=n; i++) 
        if(maxt


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved