StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
13008707
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
0
CommunityOwnedDate
CreationDate
2012-10-22T09:45:22.153
FavoriteCount
0
LastActivityDate
2012-10-22T09:45:22.153
LastEditDate
LastEditorUserId
0
OwnerUserId
1755684
ParentId
12950949
PostTypeId
2
Score
1
ViewCount
0
LastEditorDisplayName
text
Body
<p>Let us call a vertex from which all other vertices are reachable, a vista vertex. If the graph has a vista vertex, then it must have only one source SCC (since two source SCCs are not reachable from each other), which must contain the vista vertex (if its in any other SCC, there is no path from the vista vertex to the source SCC). Moreover, in this case every vertex in the source SCC will be a vista vertex. The algorithm is then simply to a DFS starting from any node and mark the vertex with the highest finishing time. This must be in a source SCC. We now again run a DFS from this vertex to check if we can reach all nodes. Since the algorithm just uses decomposition into SCCs and DFS, the running time is linear. This algorithm is correct. Note that a vista vertex will exist if and only if there is only one source SCC. Any vertex in a source SCC is only reachable by other vertices in the same SCC, so no vertex can reach vertices in two distinct source SCCs. Furthermore, if there is only one source SCC, any vertex in that SCC is a vista vertex as they are all reachable from each other. Note that a DFS that starts in any particular SCC will not finish until all of the SCCs reachable from it have been explored. This implies that the last node to finish is in a SCC that is not reachable from any other SCCs, i.e. a source SCC. Thus in the first part of our algorithm we find a node in a source SCC. By performing DFS, we will correctly determine whether or not it is a vista vertex, and if it is not a vista vertex, we know that none exist in our graph.</p>
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POUsing Strongly Connected Component Algo to check if a vertex is reachable
  singulars
  PostTypePostTypeId
  PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. This table or related slice is empty.
UserOwnerUserId
1. USantz
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
  singulars
  PostPostId
  PO
  UserUserId
  This table or related slice is empty.
  VoteTypeVoteTypeId
  VTUpMod
CommentsPostId
1. This table or related slice is empty.

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.