### Graph problem

I'd like to know what condition have I not considered in the code, this should be a DAG problem right? My code appears to be wrong in the first sample test case.Thanks a lot.

Hachiroku is a cute girl who has been a steam train driver for many years.

She has a dream. If she can make a long trip with the lovely train, No. 8620, to visit each railway exactly one time and the trip can be ended on the starting station, it will be an amazing experience.

Given a map about how railways are connected. Can you figure out if it is possible to make Hachiroku's dream come true ?

Note that each station needs to be visited at least once.

Input Format

This problem has T testcases.

For each testcase, the first line has 2 integer n,m. It means there are n stations and m railways connect between them.

In the next n lines, each line contains 2 intergers a,b . It means there is a bidirectional railway between a and b.

Output Format

Return "yes" or "no" if it is possible or not.
 ``1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768`` `````` #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; bool IsDAG (vector> const& graph) { vector in_degree(graph.size()); for (auto& tos : graph) { for (auto to : tos) { ++in_degree[to]; } } deque queue; for (uint64_t i {1}; i != graph.size(); ++i) { if (in_degree[i] == 0) { queue.push_back(i); } } while (!queue.empty()) { auto from {queue.front()}; queue.pop_front(); for (auto to : graph[from]) { if (--in_degree[to] == 0) { queue.push_back(to); } } } return (accumulate(in_degree.begin(), in_degree.end(), 0ULL) == 0); } int main() { int T,n,m; cin>>T; while(T--) { cin>>n>>m; vector> graph(n + 1); while(n--) { int a,b; cin>>a>>b; graph[a].push_back(b); } cout << (IsDAG(graph) ? "yes" : "no") <<"\n"; } return 0; } ``````
 It means there is a bidirectional railway between a and b.

You have done
` graph[a].push_back(b);`
but if it is bi-directional then you will also need to do
` graph[b].push_back(a);`
Hi, yes see that as a prob, I included the bidirection condition while it still went wrong.
Perhaps you could provide a link to the original question source ...
Last edited on
 For each testcase, the first line has 2 integer n,m. It means there are n stations and m railways connect between them. In the next n lines, each line contains 2 intergers a,b . It means there is a bidirectional railway between a and b.

There are n stations. But don't you think the second paragraph should start "In the next m lines ..."? Otherwise, m is pretty meaningless.
Last edited on
 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475`` ``````// https://en.wikipedia.org/wiki/Eulerian_path // Graph has an EULERIAN CYCLE if: // (a) every vertex has even degree; // (b) it is connected. #include #include #include using namespace std; const int startIndex = 1; // I presume //---------------------------------------------------------------------- bool isEven( const vector> &graph ) { for ( auto &e : graph ) { if ( e.size() % 2 ) return false; } return true; } //---------------------------------------------------------------------- bool isConnected( const vector> &graph ) { int n = graph.size() - startIndex; if ( n <= 1 ) return true; queue Q; vector visited( graph.size(), false ); int source = startIndex; int numVisited = 1; visited[source] = true; Q.push( source ); while ( !Q.empty() ) { int a = Q.front(); Q.pop(); for ( int b : graph[a] ) { if ( !visited[b] ) { visited[b] = true; numVisited++; if ( numVisited == n ) return true; Q.push( b ); } } } return false; } //---------------------------------------------------------------------- int main() { int T, n, m; // trials, nodes, edges cin >> T; while ( T-- ) { cin >> n >> m; vector< vector > graph( n + startIndex ); while ( m-- ) { int a, b; cin >> a >> b; graph[a].push_back(b); graph[b].push_back(a); } cout << ( isEven( graph ) && isConnected( graph ) ? "yes" : "no" ) << '\n'; } }``````

Input (based on Wikipedia example):
 ```1 6 11 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 6 4 5 5 6```

Output:
 `yes`

If you want to actually FIND the route (Eulerian cycle) then you could use backtracking (no idea if this is optimal):
 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970`` ``````// Eulerian trail: // Must visit every EDGE exactly once // Can visit every node as many times as desired // Is Eulerian cycle if start point equals end point #include #include #include using namespace std; const int startIndex = 1; // I presume const int source = startIndex; //========================================================== // Main backtracking routine bool solve( int num, int a, int m, const vector> &graph, map,bool> &edgeVisited, vector &route ) { route[num] = a; if ( num == m ) { if ( a == source ) return true; else return false; } for ( int b : graph[a] ) { if ( !edgeVisited[{a,b}] ) { edgeVisited[{a,b}] = edgeVisited[{b,a}] = true; if ( solve( num + 1, b, m, graph, edgeVisited, route ) ) return true; // Key recursion edgeVisited[{a,b}] = edgeVisited[{b,a}] = false; } } return false; } //========================================================== int main() { int T; cin >> T; while ( T-- ) { int n, m; cin >> n >> m; map,bool> edgeVisited; vector< vector > graph( n + startIndex ); vector route( 1 + m ); for ( int i = 0; i < m; i++ ) { int a, b; cin >> a >> b; graph[a].push_back(b); graph[b].push_back(a); edgeVisited[{a,b}] = edgeVisited[{b,a}] = false; } if ( solve( 0, source, m, graph, edgeVisited, route ) ) { cout << "Route: "; for ( auto e : route ) cout << e << " "; cout << '\n'; } else { cout << "No Eulerian cycle\n"; } } }``````

With the same input as above this gives:
 `Route: 1 2 3 1 4 2 5 4 3 6 5 1 `

Last edited on
Hello, yes I think it should be m, must be typo mistake. Thank you for your provided solutions and also the backtracking idea. The problem is solved.
Topic archived. No new replies allowed.