Finding a cycle in a graph

[barneyTdino]

I'm given a graph, where the points are connected by edges given by numbers like:

1 3
2 19
8 12
etc.

The method prescribed to find the graph is to set a vector<vector<int> > adj, where adj[1][3] = 1 and adj[3][1] =1, ie, adjacency is true for vertices 1 and 3, and so on.

the condition is that the starting and ending vertex is 1.

My method is to:

1. read the file
2. push the data into two vectors of 100 entries. Also, define an adjacency vector adj where all adjacent edges give 1. This is required from the question.
3. declare a starting number, z =1
4. use a for loop to find a number for which adj[i][z] = 1 or adj[z][i] = 1.
5. update z.

However, I have a few problems.
1. This is clearly the wrong code.
2. I don't have a method to end at 1.
3. The if expression that you see there only meets the adj[i][z]=1 condition but can't account for the other condition.

Can someone help, please? Is there a better way to do this without the additional vectors a and b??

    
int main()
{
    vector<vector<int> > adj(101);
    vector<int> a;
    vector<int> b;
    
    for(int i=1;i<=100;i++)
            adj[i].resize(101);
 
    ifstream in("data.txt");
    int x,y;
    while(in >> x >> y)
    {
             a.push_back(x);
             b.push_back(y);
             adj[x][y]=1;
             adj[x][y]=1;
    }

    
    int z;
    z =1;
    cout << z << " ";
    
    for(int i=0;i<100;i++)
    {
            
            if(adj[z][i] == 1 && b[i-1]==z && a[i-1] != z)
            {
                cout << a[i-1] << " ";
                start = a[i-1];
            }
            
    }

}

[firedraco]

You could use a vector of pairs:

std::vector< std::pair<int, int> > edges;

Then what you could do as start at any point (e.g., edges[0].first), and then loop through the rest of the vector, and check to see if there are any points edges[0].second connects to. Then repeat until you find a point that connects to edges[0].first (or if you want, and of the subsequent points).

[barneyTdino]

There is a problem. In fact I've tried this problem a number of ways and I can't get the answer. If I know my cycle has, say, 20 points, the program finds just 5, and the last one is incorrect. I'm not sure why. I keep getting the same thing no matter how I do it. I think it is because I keep looking in one direction but not the other.

Really vexed with this. Could you check my code? This is using the method you suggested.

    vector<pair<int,int> > point;
    vector<int> a;
    vector<int> b;
    int current;
    int start =0;
 

int main(int argc, char *argv[])
{
 
    ifstream in("data.txt");
    int buffer1,buffer2;
    while(in >> buffer1 >> buffer2)
    {
             a.push_back(buffer1);
             b.push_back(buffer2);
    }
    
    point.resize(a.size());
    
    for(int i=0;i<a.size();i++)
    {
            point[i].first = a[i];
            point[i].second = b[i];
    }
    
    for(int i=0;i<point.size();i++)
    {
            if(point[i].second == point[start].first)
            {
                cout << point[i].second << " ";
                start = i;
            }
    }