# Paste: graph theory question

Author: slava text Mon, 3 Aug 2009 15:49:09
Plain Text |
```Suppose I have a graph G = (V,E). There might be multiple edges between two vertices.

Given a set of edges X, I want to find the set of vertices W in V such that for w in W, there is a cycle that starts and ends at w with at least one edge of the cycle contained in X.```

Author: anonymous text Mon, 3 Aug 2009 16:09:08
Plain Text |
```it doesn't matter in a cycle if something "starts or ends" it.

If you have another idea of what starts or ends mean, then encode it. Otherwise, don't worry, you just want w to be part of a cycle of the edges in X ```

## Annotation: solution, maybe

Author: littledan factor Mon, 3 Aug 2009 17:31:56
Plain Text |
```1. Calculate the strongly connected components of the graph. This partitions the set of edges
2. Find the components for each member of X
3. Take their union, and get the set of vertices that any of the edges touch

You can get strongly connected components with Tarjan's algorithm:
http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
Tarjan's algorithm seems to allow partial computation of SCCs: it's easy to just calculate the components which go through X, and not incur cost for the other components.```

## Annotation: Not sure

Author: Not sure factor Mon, 3 Aug 2009 20:08:27
Plain Text |
`Not sure that's right littledan but I don't have a better solution :-)`