CS Academy Bad Triplet

题目链接：https://csacademy.com/contest/archive/task/bad-triplet

题目大意：给出一个无向连通图，每条边的长度为1.现在要求找出来三个点A,B,C满足任意两个点的最短距离相等，即mindis(A, B) ==mindis(B,C) == mindis(A,C).如果存在这样的点，输出这三个点的标号。否则输出-1.

解题思路：可以发现，如果有一个点度（包括出度和入度）大于等于3并且没有构成环，那么显然与其相连的任意三个点都满足条件；若有度为3的点但是其中两个与之构成了环，那么输出构成环的三个点即可。否则判断整个图是否为环并且n为3的倍数即可。

代码：

 1 const int maxn = 3e5 + 5;
 2 int n, m;
 3 int deg[maxn];
 4 set<int> a[maxn / 2];
 5 
 6 void solve(){
 7     VI ansv;
 8     bool atwo = true, ans = false;
 9     for(int i = 1; i <= n; i++){
10         if(deg[i] >= 3){
11             ans = true;
12             set<int>::iterator it;
13             for(it = a[i].begin(); it != a[i].end(); it++){
14                 int u = *it, tmp = ansv.size();
15                 if(tmp == 0)
16                     ansv.push_back(u);
17                 else if(tmp == 1){
18                     if(a[u].find(ansv[0]) != a[u].end())
19                         ansv.push_back(i);
20                     ansv.push_back(u);
21                 }
22                 else if(tmp == 2){
23                     if(a[u].find(ansv[0]) != a[u].end()){
24                         ansv[1] = i;
25                     }
26                     else if(a[u].find(ansv[1]) != a[u].end()){
27                         ansv[0] = i;
28                     }
29                     ansv.push_back(u);
30                 }
31                 if(ansv.size() >= 3) break;
32             }
33             break;
34         }
35         if(deg[i] == 1) atwo = false;
36     }
37     if(ans){
38         for(int i = 0; i < ansv.size(); i++) {
39             if(i != 0) printf(" ");
40             printf("%d", ansv[i]);
41         }
42         puts("");
43         return;
44     }
45     if(atwo){
46         if(n % 3 != 0){
47             puts("-1");
48             return;
49         }
50         else{
51             for(int i = 1; i <= n; i += n / 3){
52                 if(i != 1) printf(" ");
53                 printf("%d", i);
54             }
55             puts("");
56             return;
57         }
58     }
59     puts("-1");
60 }
61 int main(){
62     scanf("%d %d", &n, &m);
63     for(int i = 0; i < m; i++){
64         int u, v;
65         scanf("%d %d", &u, &v);
66         a[u].insert(v); a[v].insert(u);
67         deg[u] += 1;
68         deg[v] += 1;
69     }
70     solve();
71 }

题目：

Bad Triplet

Time limit: 1000 ms
Memory limit: 128 MB

You are given a simple, undirected, connected graph with

Standard input

The first line contains two integer

Each of the next

Standard output

If there is no solution output

Otherwise print three distinct integers, representing the nodes

Constraints and notes

$10^51≤N,M≤105$

Input	Output
8 8 1 6 6 3 3 4 4 5 4 7 7 8 8 1 5 2	1 7 3
3 2 1 3 2 3	-1