Graph problem

[Pen72]

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.

  #include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

bool IsDAG (vector<vector<uint64_t>> const& graph)
{
  vector<uint64_t> in_degree(graph.size());
  for (auto& tos : graph)
  {
    for (auto to : tos) { ++in_degree[to]; }
  }
  deque<uint64_t> 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<vector< uint64_t>> graph(n + 1);
        while(n--)
        {
            int a,b;
            cin>>a>>b;
            graph[a].push_back(b); 
            
        }
        cout << (IsDAG(graph) ? "yes" : "no") <<"\n";
    }
    return 0;
}

[lastchance]

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);

[Pen72]

Hi, yes see that as a prob, I included the bidirection condition while it still went wrong.

[lastchance]

Perhaps you could provide a link to the original question source ...

[lastchance]

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.

[lastchance]

// https://en.wikipedia.org/wiki/Eulerian_path
// Graph has an EULERIAN CYCLE if:
// (a) every vertex has even degree;
// (b) it is connected.


#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int startIndex = 1;         // I presume

//----------------------------------------------------------------------

bool isEven( const vector<vector<int>> &graph )
{
   for ( auto &e : graph )
   {
      if ( e.size() % 2 ) return false;
   }
   return true;
}

//----------------------------------------------------------------------

bool isConnected( const vector<vector<int>> &graph )
{
   int n = graph.size() - startIndex;   if ( n <= 1 ) return true;
   
   queue<int> Q;
   vector<bool> 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<int> > 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):

// 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 <iostream>
#include <vector>
#include <map>
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<vector<int>> &graph, map<pair<int,int>,bool> &edgeVisited, vector<int> &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<pair<int,int>,bool> edgeVisited;
      vector< vector<int> > graph( n + startIndex );
      vector<int> 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 

[Pen72]

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.