第一行，两个整数N，M 表示有N个顶点和M个三角形 (3<=N<=400, 1<=M<800)
接下来M行，每行三个数字Ai, Bi, Ci(1<=Ai<=N, 1<=Bi<=N, 1<Ci<=N)，表示第i个三角形的顶点序号
输出M行，每行三个数字，表示调整后的三角形顶点索引，输出的三角形顺序需要和输入保持一致。
6 4 3 2 4 1 3 2 3 6 5 5 3 4
2 4 3 1 2 3 3 5 6 3 4 5
#include<iostream>
#include<vector>
using namespace std;
//找出三角形最小顶点位置
int minx(vector<int> tri){
if(tri[0] < tri[1] && tri[0] < tri[2]){
return 0;
}
else if(tri[1] < tri[0] && tri[1] < tri[2]){
return 1;
}
else return 2;
}
//将三角最小顶点位置移动到头部
void move(vector<int> &tri){
int x = minx(tri);
if(x == 1){
int temp = tri[0];
tri[0] = tri[1];
tri[1] = tri[2];
tri[2] = temp;
}
if(x == 2){
int temp = tri[1];
tri[1] = tri[0];
tri[0] = tri[2];
tri[2] = temp;
}
return;
}
//调换三角形三个顶点顺序
void change(vector<int> &tri){
int temp = tri[0];
tri[0] = tri[2];
tri[2] = temp;
return;
}
void func(int num,vector<vector<int>> &triangle){
move(triangle[num]);//将当前三角形最小顶点到开头，其他顶点也相应变换
triangle[num][3] = 1;//表明该三角形已经修改过
for(int i = 0; i < triangle.size(); i++){
//对于遍历、修改过的三角形
if(triangle[i][3] == 1) continue;
else{
for(int j = 0; j < 3; j++){
//该三角形与num三角形相邻且旋转顺序相反
if((triangle[i][j%3] == triangle[num][0] && triangle[i][(j+1)%3] == triangle[num][1])
||(triangle[i][j%3] == triangle[num][1] && triangle[i][(j+1)%3] == triangle[num][2])
||(triangle[i][j%3] == triangle[num][2] && triangle[i][(j+1)%3] == triangle[num][0])){
//调换顺序
change(triangle[i]);
//把最小的放在最前面
func(i,triangle);
}
//该三角形与num三角形相邻且旋转顺序相同
else if((triangle[i][j%3] == triangle[num][1] && triangle[i][(j+1)%3] == triangle[num][0])
||(triangle[i][j%3] == triangle[num][2] && triangle[i][(j+1)%3] == triangle[num][1])
||(triangle[i][j%3] == triangle[num][0] && triangle[i][(j+1)%3] == triangle[num][2])){
func(i,triangle);
}
//该三角形与num三角形不相邻 不管
}
//for 遍历一个三角形
}
}//for 遍历所有三角形
return;
}
int main(){
int N,M;
scanf("%d%d",&N,&M);
vector<vector<int>> triangle(M,vector<int>(4,0));
int m = 0;
while(m < M){
scanf("%d%d%d",&triangle[m][0],&triangle[m][1],&triangle[m][2]);
m++;
}
func(0,triangle);
m=0;
while(m < M){
cout << triangle[m][0] <<" "<< triangle[m][1] << " " << triangle[m][2] << endl;
m++;
}
return 0;
} 构造三叉树并使用bfs搜索，但是对于判断相邻的三角形是否同向比较笨拙，需要改进
import sys
class Node():
def __init__(self, index, vertex):
self.index = index
self.vertex = vertex
self.children = []
self.visited = False
self.rotated = False
def rotate(self):
self.vertex = [self.vertex[0], self.vertex[2], self.vertex[1]]
def order(self):
ind = self.vertex.index(min(self.vertex))
if ind==1:
self.vertex = [self.vertex[1], self.vertex[2], self.vertex[0]]
elif ind==2:
self.vertex = [self.vertex[2], self.vertex[0], self.vertex[1]]
# print(self.vertex)
## 构造边列表加速查询
edges = dict({})
nodes = []
N, M = map(int, sys.stdin.readline().split())
# 三叉树
for i in range(M):
tri = list(map(int, sys.stdin.readline().split()))
nodes.append(Node(i, tri))
# 查询是否有相邻三角
for j in range(3):
v1, v2 = tri[j], tri[(j+1)%3]
if v1 > v2:
v1, v2 = v2, v1
if (v1, v2) in edges:
nodes[edges[(v1, v2)]].children.append((v1, v2, i))
nodes[i].children.append((v1, v2, edges[(v1, v2)]))
else:
edges[(v1, v2)] = i
# BFS
neighbor = []
neighbor.append(nodes[0])
nodes[0].order()
nodes[0].rotated = True
while len(neighbor)!=0:
node = neighbor.pop()
node.visited = True
for i in node.children:
if nodes[i[2]].visited==False:
# 旋转方向并入栈
if nodes[i[2]].rotated==False:
edge = i[0:2]
ind0, ind1 = node.vertex.index(edge[0]), node.vertex.index(edge[1])
in0, in1 = nodes[i[2]].vertex.index(edge[0]), nodes[i[2]].vertex.index(edge[1])
# print(ind0, ind1, in0, in1, ((ind1-ind0+3)%3), ((in1-in0+3)%3))
if ((ind1-ind0+3)%3) == ((in1-in0+3)%3):
nodes[i[2]].rotate()
nodes[i[2]].order()
nodes[i[2]].rotated = True
neighbor.append(nodes[i[2]])
for i in range(M):
print(' '.join(map(str, nodes[i].vertex)))
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Solution_for_LeiHuo {
public:
void sort_triangle() {
int N,M; cin >> N >> M;
vector<vector<int>> directions(N + 1, vector<int>(N + 1,0));
vector<vector<int>> triangles;
for (int i = 0; i < M; ++ i) {
vector<int> triangle;
int a,b,c;
cin >> a >> b >> c;
triangle.push_back(a);
triangle.push_back(b);
triangle.push_back(c);
triangles.push_back(triangle);
}
for (int i = 0; i < 3; ++ i) {
directions[triangles.front()[i]][triangles.front()[(i + 1) % 3]] = 1;
directions[triangles.front()[(i + 1) % 3]][triangles.front()[i]] = -1;
}
queue<int> q;
for (int i = 1; i < M; ++ i) q.push(i);
change_triangle_seq(triangles[0]);
while (!q.empty()) {
int index = q.front();
vector<int>& tri = triangles[index];
int ret = is_legal_direction(tri, directions);
if (ret == 1) {
change_triangle_seq(tri);
} else if (ret == -1) {
reverse_triangle(tri);
} else {
q.push(index);
}
q.pop();
}
for (vector<int> v : triangles) {
cout << v[0] << " " << v[1] << " " << v[2] << endl;
}
}
private:
void reverse_triangle(vector<int> & triangle) {
swap(triangle[0], triangle[2]);
change_triangle_seq(triangle);
}
// change the sequence of vertexes, in order to make the min vertex the first place
void change_triangle_seq(vector<int> & triangle) {
int min = 0;
for (int i = 1; i < 3; ++ i) {
if( triangle[i] < triangle[min] ) min = i;
}
if (min == 1) {
swap(triangle[0], triangle[1]);
swap(triangle[1], triangle[2]);
} else if (min == 2) {
swap(triangle[0], triangle[2]);
swap(triangle[1], triangle[2]);
}
}
// to tell whether the given triangle is in the same direction as the first triangle
int is_legal_direction(vector<int> tri, vector<vector<int>>& directions) {
int ret = 0;
for (int i = 0; i < 3; ++ i) {
if (directions[tri[i]][tri[(i + 1) % 3]]) {
ret = -1 * directions[tri[i]][tri[(i + 1) % 3]];
break;
}
}
if (ret) {
for (int i = 0; i < 3; ++ i) {
directions[tri[i]][tri[(i + 1) % 3]] = ret;
directions[tri[(i + 1) % 3]][tri[i]] = -1 * ret;
}
}
// if ret = 1, two triangles are in the same direction
// if -1, not
// if 0, can not tell yet, should be judged later
return ret;
}
};
int main() {
Solution_for_LeiHuo solutionForLeiHuo;
solutionForLeiHuo.sort_triangle();
} 
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int f[3];
void adjust()
{
int minval = min(f[0], min(f[1], f[2]));
while (minval != f[0])
{
swap(f[0], f[1]);
swap(f[1], f[2]);
}
}
void rotate(int l, int r)
{
int i = find(l), j = find(r);
for (int k = 0; k < 3; ++k)
{
if (k != i && k != j)
{
f[0] = f[k];
break;
}
}
f[1] = l, f[2] = r;
adjust();
}
int find(int x)
{
for (int i = 0; i < 3; ++i)
{
if (f[i] == x)
{
return i;
}
}
return -1;
}
};
const int N = 1e3 + 7;
int n, m;
Node nodes[N];
bool st[N];
map<pair<int, int>, vector<int>> maps;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++i)
{
scanf("%d%d%d", &nodes[i].f[0], &nodes[i].f[1], &nodes[i].f[2]);
for (int j = 0; j < 2; ++j)
{
for (int k = j + 1; k < 3; ++k)
{
pair<int, int> key = {min(nodes[i].f[j], nodes[i].f[k]), max(nodes[i].f[j], nodes[i].f[k])};
maps[key].push_back(i);
}
}
}
queue<int> que;
que.push(0);
st[0] = 1;
while (!que.empty())
{
int u = que.front();
que.pop();
nodes[u].adjust();
for (int i = 0; i < 3; ++i)
{
int j = (i + 1) % 3;
pair<int, int> key = {min(nodes[u].f[i], nodes[u].f[j]), max(nodes[u].f[i], nodes[u].f[j])};
for (auto ne : maps[key])
{
if (st[ne])
{
continue;
}
nodes[ne].rotate(nodes[u].f[j], nodes[u].f[i]);
st[ne] = 1;
que.push(ne);
}
}
}
for (int i = 0; i < m; ++i)
{
printf("%d %d %d\n", nodes[i].f[0], nodes[i].f[1], nodes[i].f[2]);
}
return 0;
}
// 三角网格.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
这样写有什么不对吗
#include <iostream>
using namespace std;
#include<vector>
#include<algorithm>
int main()
{
int N, M;
//cout << "请输入N个顶点和M个三角形：" << endl;
cin >> N >> M;
int a, b, c;
vector<vector<int>>res;
vector<int>dic(M);
dic[0] = 1;
for (int i = 0; i < M;i++) {
//cout << "输入三角形：" << endl;
vector<int>path;
cin >> a >> b >> c;
path.push_back(a);
path.push_back(b);
path.push_back(c);
res.push_back(path);
}
for (int i = 0; i < res.size(); i++) {
if (dic[i] == 0) continue;
int a = res[i][0];
int b = res[i][1];
int c = res[i][2];
for (int j = 0; j < res.size(); j++) {
if (i == j||dic[j]!=0) continue;
auto it1 = find(res[j].begin(),res[j].end(),a);
auto it2 = find(res[j].begin(), res[j].end(), b);
auto it3= find(res[j].begin(), res[j].end(), c);
int pre, last;
if (it1 != res[j].end() && it2 != res[j].end()) {
pre = it1 - res[j].begin();
last = it2 - res[j].begin();
int temp = last - pre;
if (temp == 1 || temp == -2) {//相对位置保持不变，且相差距离为1
dic[j] = -dic[i];
}
if (temp == -1 || temp==2) {//相对位置改变，且相差距离为1
dic[j] = dic[i];
}
}
else if (it1 != res[j].end() && it3 != res[j].end()) {
pre = it1 - res[j].begin();
last = it3 - res[j].begin();
int temp = last - pre;
if (temp == -1 || temp == 2) {//相对位置保持不变，且相差距离为1
dic[j] = -dic[i];
}
if (temp == 1 || temp == -2) {//相对位置改变，且相差距离为1
dic[j] = dic[i];
}
}
else if(it2 != res[j].end() && it3 != res[j].end()) {
pre = it2 - res[j].begin();
last = it3 - res[j].begin();
int temp = last - pre;
if (temp == 1 || temp == -2) {//相对位置保持不变，且相差距离为1
dic[j] = -dic[i];
}
if (temp == -1 || temp == 2) {//相对位置改变，且相差距离为1
dic[j] = dic[i];
}
}
else
{
continue;
}
}
}
//cout << "-----------" << endl;
for (int i = 0; i < res.size(); i++) {
if (dic[i] == -1) {
reverse(res[i].begin(),res[i].end());
}
int minvalue = *min_element(res[i].begin(), res[i].end());
auto it = find(res[i].begin(),res[i].end(),minvalue);
vector<int> temp(res[i].begin(),it);
vector<int> ans(it,res[i].end());
for (int j = 0; j < ans.size(); j++) {
cout << ans[j] << " ";
}
for (int k = 0; k < temp.size(); k++) {
cout << temp[k] << " ";
}
cout << endl;
}
}
#include<bits/stdc++.h>
using namespace std;
class triangle{
public:
triangle():point_1(0),point_2(0),point_3(0){};
triangle(int a,int b,int c):point_1(a),point_2(b),point_3(c){};
void _change_order();
void _change_direction(triangle& reference);
bool flag=false;
int point_1;
int point_2;
int point_3;
bool _common_line(triangle& reference);
};
bool triangle:: _common_line(triangle& reference){
int count=0;
if(point_1==reference.point_1){
++count;
}
else if(point_1==reference.point_2){
++count;
}
else if(point_1==reference.point_3){
++count;
}
if(point_2==reference.point_1){
++count;
}
else if(point_2==reference.point_2){
++count;
}
else if(point_2==reference.point_3){
++count;
}
if(point_3==reference.point_1){
++count;
}
else if(point_3==reference.point_2){
++count;
}
else if(point_3==reference.point_3){
++count;
}
if(count==2) return true;
else return false;
}
void triangle:: _change_order(){
if(point_2<point_1&&point_2<point_3){
int tmp=point_1;
point_1=point_2;
point_2=point_3;
point_3=tmp;
}
else if(point_3<point_1&&point_3<point_2){
int tmp=point_3;
point_3=point_2;
point_2=point_1;
point_1=tmp;
}
}
void triangle:: _change_direction(triangle& reference){
if(_common_line(reference)){
if(point_1==reference.point_1&&point_2==reference.point_2){
int tmp=point_1;
point_1=point_2;
point_2=tmp;
}
else if(point_1==reference.point_3&&point_2==reference.point_1){
int tmp=point_1;
point_1=point_2;
point_2=tmp;
}
else if(point_1==reference.point_2&&point_2==reference.point_3){
int tmp=point_1;
point_1=point_2;
point_2=tmp;
}
else if(point_1==reference.point_1&&point_3==reference.point_3){
int tmp=point_1;
point_1=point_3;
point_3=tmp;
}
else if(point_1==reference.point_2&&point_3==reference.point_1){
int tmp=point_1;
point_1=point_3;
point_3=tmp;
}
else if(point_1==reference.point_3&&point_3==reference.point_2){
int tmp=point_1;
point_1=point_3;
point_3=tmp;
}
else if(point_2==reference.point_1&&point_3==reference.point_2){
int tmp=point_2;
point_2=point_3;
point_3=tmp;
}
else if(point_2==reference.point_2&&point_3==reference.point_3){
int tmp=point_2;
point_2=point_3;
point_3=tmp;
}
else if(point_2==reference.point_3&&point_3==reference.point_1){
int tmp=point_2;
point_2=point_3;
point_3=tmp;
}
flag=true;
}
}
void Main();
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie();
Main();
return 0;
}
void Main(){
int m,n;
cin>>m>>n;
vector<triangle> _array;
for(int i=0;i!=n;i++){
int a,b,c;
cin>>a>>b>>c;
_array.emplace_back(triangle(a,b,c));
}
_array[0].flag=true;//第一个输入三角形不变方向
_array[0]._change_order();
for(int i=0;i!=n;i++){
if(_array[i].flag==false) continue;
for(int j=1;j!=n;j++){
if(_array[j].flag==false){
_array[j]._change_direction(_array[i]);
_array[j]._change_order();
//cout<<i<<j<<endl;
}
}
}
for(;;){
vector<int> _false;
vector<int> _true;
for(int i=0;i!=n;i++){
if(_array[i].flag==false) _false.emplace_back(i);
else _true.emplace_back(i);
}
if(_false.empty()) break;
for(int i:_true){
for(int j:_false){
if(_array[j]._common_line(_array[i])){
_array[j]._change_direction(_array[i]);
_array[j]._change_order();
}
}
}
}
for(int i=0;i!=n;i++){
if(_array[i].flag==false) cout<<i<<endl;
}
for(int i=0;i!=n;i++){
cout<<_array[i].point_1<<' '<<_array[i].point_2<<' '<<_array[i].point_3<<endl;
}
}
#include <iostream>
#include <vector>
#include <map>
#include <tuple>
#include <utility>
using namespace std;
void dfs(map<pair<int, int> ,pair<int, int>>& m, vector<vector<int>>& triangles, vector<bool>& faceTrue,int left, int right){
auto indexs = m[{left, right}];
if(!faceTrue[indexs.first]){
int i = 0;
while(triangles[indexs.first][i] != left){
i++;
}
if(triangles[indexs.first][(i+1)%3] == right){
swap(triangles[indexs.first][1],triangles[indexs.first][2]);
}
faceTrue[indexs.first] = true;
dfs(m, triangles, faceTrue, triangles[indexs.first][0], triangles[indexs.first][1]);
dfs(m, triangles, faceTrue, triangles[indexs.first][1], triangles[indexs.first][2]);
dfs(m, triangles, faceTrue, triangles[indexs.first][2], triangles[indexs.first][0]);
}
if(indexs.second > 0 && !faceTrue[indexs.second]){
int i = 0;
while(triangles[indexs.second][i] != left){
i++;
}
if(triangles[indexs.second][(i+1)%3] == right){
swap(triangles[indexs.second][1],triangles[indexs.second][2]);
}
faceTrue[indexs.second] = true;
dfs(m, triangles, faceTrue, triangles[indexs.second][0], triangles[indexs.second][1]);
dfs(m, triangles, faceTrue, triangles[indexs.second][1], triangles[indexs.second][2]);
dfs(m, triangles, faceTrue, triangles[indexs.second][2], triangles[indexs.second][0]);
}
}
int main() {
int N = 0, M = 0;
cin >> N >> M;
vector<vector<int>> triangles(M, vector<int>(3));
vector<bool> faceTrue(M, false);
faceTrue[0] = true;
map<pair<int, int> ,pair<int, int>> m;
for(int i = 0 ; i < M; i++){
int a, b, c;
cin >> a >> b >> c;
if(a <= b && a <= c){
triangles[i][0] = a;
triangles[i][1] = b;
triangles[i][2] = c;
}else if (b <= a && b <=c) {
triangles[i][0] = b;
triangles[i][1] = c;
triangles[i][2] = a;
}else if (c <= a && c <= b) {
triangles[i][0] = c;
triangles[i][1] = a;
triangles[i][2] = b;
}
if(m.find({a,b}) == m.end()){
m[{a,b}] = {i, -1};
m[{b,a}] = {i, -1};
}else{
m[{a,b}].second = i;
m[{b,a}].second = i;
}
if(m.find({b,c}) == m.end()){
m[{b,c}] = {i,-1};
m[{c,b}] = {i,-1};
}else{
m[{b,c}].second = i;
m[{c,b}].second = i;
}
if(m.find({c,a}) == m.end()){
m[{c,a}] = {i,-1};
m[{a,c}] = {i,-1};
}else{
m[{c,a}].second = i;
m[{a,c}].second = i;
}
}
dfs(m, triangles, faceTrue, triangles[0][0], triangles[0][1]);
dfs(m, triangles, faceTrue, triangles[0][1], triangles[0][2]);
dfs(m, triangles, faceTrue, triangles[0][2], triangles[0][0]);
for(int i = 0; i < M; i++){
cout << triangles[i][0] <<" " << triangles[i][1] << " " << triangles[i][2] << endl;
}
return 0;
}
class Triangle(object): def __init__(self,A,B,C): self.A,self.B,self.C=A,B,C # edge(0~2): AB BC CA # edgeinv(0~2) BA CB AC def edge(self, ii): if ii==0: return (self.A,self.B) elif ii==1: return (self.B,self.C) else: return (self.C,self.A) def edgeinv(self, ii): if ii==0: return (self.B,self.A) elif ii==1: return (self.C,self.B) else: return (self.A,self.C) def reorder(self,order): # put minimum first and reorder A,B,C=self.A,self.B,self.C if A<B and A<C: return (A,B,C) if order==1 else (A,C,B) elif B<A and B<C: return (B,C,A) if order==1 else (B,A,C) else: return (C,A,B) if order==1 else (C,B,A) def IsConnect(Tr1,Tr2): ## -1: connet and order inverse ## not connect ## 1 : connet and order is the same for i in range(3): for j in range(3): if Tr1.edge(i)==Tr2.edge(j): return 1 if Tr1.edge(i)==Tr2.edgeinv(j): return -1 return 0 line1=input() N,M=int(line1.split()[0]), int(line1.split()[1]) Triangles=[ ] for idx in range(M): line = input() ss=line.split() A,B,C = int(ss[0]),int(ss[1]),int(ss[2]) Triangles.append( Triangle(A,B,C) ) ### 1: known right 0: unknown -1: known, need inverse order = [ 0 for i in range(M) ] order[0]=1 temp=[0] newtemp=[] while 0 in order: for i in [ i for i in range(M) if order[i]==0 ]: #for unknown order for j in temp: connectij=IsConnect(Triangles[i],Triangles[j]) if connectij!=0: # find connected triangle order[i]=-1*order[j]*connectij newtemp.append(i) break temp=newtemp newtemp=[] for i in range(M): v1,v2,v3=Triangles[i].reorder(order[i]) print(v1,v2,v3)
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
