CareerCup

Given a graph G=(V,E)
-Find strongly connected components in G
-Replace each SCC with a vertex, G become a directed acrylic graph (DAG)
-Topological sort on DAG
-If there is an edge between each pair of vertices(v[i],v[i+1]) then the given graph is semi-connected

Create adjacency matrix with number given to each of the vertices.
Graph is semi-connected
foreach i,j
if(i!=j && (a[i][j] || a[j][i])

1)create path[][] array based on edge[][].
2)Check whether it is semi-connected.

for(i=0;i<n;i++)DFS(path,i,i);
void DFS(int[][]path,int root,int current)
{
for(j=0;j<n;j++) if(edge[current][j]==1){path[current][j]=1;
DFS(path,root,j);}
}

This looks a classic problem of Network Flows: We can take a node at random in the graph and imagine it to be a source which has unlimited flow coming into it, and the corresponding edges can be used to direct the flow of water from this source and to wherever the water comes out we can think of this as the connected nodes and we can remove them from the graph and if there is atleast 1 node left which is not connected we can call it as v now in the orignal graph check if there is a path from v to u, if there exists then it is a semi connected and if there doesn't exist then it is not a semi connected graph.

the running time of this algorithm is O(n square) where n is the number of nodes in the graph.

you can use DFS to check if there are backward edges - happens if you encounter a node that is already visited but not explored. If you are able to traverse through the entire graph without any backward edges then its semi-connected

i=0 to <n
j=0 to i
if ( a[i][j]&&a[j][i] ) !=1
print not semi connected ; break ;

sry wrong ans ... my bad

hxxp://cs.sunysb.edu/~jgao/CSE548-fall08/homework1-soln.pdf

Can't we solve this using lists similar to adjacency lists. Every node has a list of all its connected nodes. For every vertex v, if u is reachable from v, u will be in the list of v. On the other hand, if v is reachable from u, then, v will be in the list of u. After visiting all the nodes of the graph (using DFS may be), we need to scan each vertex's list & see who is reachable & not. This may require another data structure. Complexity defenitely sucks in this approach.

bool issemiconnected(graph[n][n])
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
  {
     if(i==j)
     continue;
     else
      {if( ! ( graph[i][j] || graph[j][i] )
          {
        return false;
          }
       }
   }
}
return true;
}