CODEWITHSUNDEEP
c++algorithmgraph-algorithmeuler-path
yoons
yoons

Reputation: 25

i made Eulerian path algorithm(Euler-path). what's the problem?

I made an Eulerian path algorithm, what's the problem?

#include <cstdio>
#include <vector>
#include <iostream>
#include <list>
using namespace std;
int graph[1000][1000];  // 1<n<1000
int n; // 그래프는 n x n 
int i, j, degree[1000] = {},f=1;
list<int> lt1;
void oiler(int u) {
        for(int v=0;v<n;v++){
            while (graph[u][v]>0) {
                graph[u][v]--;
                graph[v][u]--;
                oiler(v);
                }
        }
        lt1.push_back(u);
 }
int main(void) {
    cin >> n;
    for (i = 0; i < n; i++) { 
        for (j = 0; j < n; j++) {
            cin >> graph[i][j];
            sum += graph[i][j]; 
        }
    }
    oiler(0);
    lt1.reverse();
    list<int>::iterator iter = lt1.begin();
    for(iter=lt1.begin(); iter!=lt1.end(); iter++) 
    { 
        printf("%d ", *iter+1);
    } 
}

input is

6 
0 1 0 1 1 1
1 0 1 1 1 0
0 1 0 1 0 0
1 1 1 0 1 0
1 1 0 1 0 1
1 0 0 0 1 0

output is

1 2 3 4 1 5 2 4 5 6 1

it makes works and makes true output but not passed ... let me know if i missed anything

Upvotes: 0

Views: 251

Answers (2)

Swift - Friday Pie
Swift - Friday Pie

Reputation: 14688

You're missing definition of sum, this could not compile. Did you initialize it? Was it your intention to add 1 to every element: *iter+1?

Also you're wasting time on reversing list. You just can use push_front for std::list. In other cases you can also iterate in reverse order. In C++20 with its std::views::

// needs #include <ranges>

for (auto const& item : lt1| std::views::reverse) {
    std::cout << item << " ";
}

In C++11:

for (auto iter = lt1.rbegin(), ei = lt1.rend(); iter != ei; ++iter) {
     std::cout << *iter << " ";
}

For repeated use there are some way to do it through adapters.

Upvotes: 2

schorsch312
schorsch312

Reputation: 5714

I assume, that you are doing an online coding challenge and that some visible tests pass, but the entire testsuite fails, right? Please update your problem describtion in order to make clear what your error is.

Nevertheless,

for(iter=lt1.begin(); iter!=lt1.end(); iter++) 
{ 
    printf("%d ", *iter+1);
}

is a bad idea, since your are trying to read beyond the end of the list. You will not find meaningful data there, especially if the list is empty (n==0).

Try

for (auto const& item : lt1)
{
    std::cout << item;
}

Upvotes: 1

Related Questions