Отримай дерево
Одна из моих студенток написала неправильное решение, но оно зашло. Например, на таком простом тесте
4 5 1 2 2 3 3 4 4 1 1 3
это решение даёт такой ответ:
1 2 3 4
В тесте граф в виде квадрата с одной диагональю. Её решение оставляет только два из пяти рёбер (а должно было оставить три), причём получается даже не дерево, а лес!
Это означает, что и чекер плохой, так как не следит за количеством рёбер, и тесты плохие, так как не содержат в себе таких тривиальных случаев.
решение#2572135 посмотрите решение,я там ничего не написал,но оно прошло на 100%,все решения проходят на 100% даже если они неправильны
Нужно что-то делать в организационном плане. Очевидная ошибка не должна висеть два года. Лучше просто убирать такие задачи, чтобы сохранить (повысить) репутацию сайта.
include <bits/stdc++.h>
using namespace std; int main() { int n,m,x,y,po,t; cin>>n>>m; int f[n][n], w[n]; stack <int> ruh; for (int i=0;i<n;i++) { w[i]=0; for (int j=0;j<n;j++) { f[i][j]=0; } } for (int i=0;i<m;i++) { cin>>x>>y; f[x-1][y-1]=1; f[y-1][x-1]=1; } cin>>po; ruh.push(po-1); while (ruh.size()>0) { if (w[ruh.top()]==0) { cout<<ruh.top()+1<<" "; } w[ruh.top()]=1; t=0; for (int j=0;j<n;j++) { if (f[ruh.top()][j]==1 && w[j]==0) { ruh.push(j); t++; break; } } if (t==0) { ruh.pop(); } } }