Question

In: Computer Science

Please use python: # Problem Description Given a directed graph G = (V, E), find the...

Please use python:

# Problem Description

Given a directed graph G = (V, E), find the number of connected components in G.

# Input

The graph has `n` vertices and `m` edges.
There are m + 1 lines, the first line gives two numbers `n` and `m`, describing the number of vertices and edges. Each of the following lines contains two numbers `a` and `b` meaning there is an edge (a,b) belong to E. All the numbers in a line are separated by space. (`1 <= a,b <= n`)

You can assume that 2 <= n <= 10000, 1 <= m <= 50000.

Your code should read the input from standard input (e.g.
using functions `input()/raw_input()` in Python and `cin/scanf` in C++).

# Output

One number representing the number of connected components in the graph.


Your code should write the output to standard output (e.g. using functions `print` in Python and `cout/printf` in C++).

# Requirement

Your algorithm should run in O(|V| + |E|) time.

Time limtation: 5 seconds.

Memory limitation: 1.0 GB.

# Environment

Your code will be running on Ubuntu 18.04.5.

Now only accept C++ and Python2/Python3 code, g++ version 7.5.0 and Python versions are Python 2.7.17 and Python 3.6.9.

# Examples and Testing

Some examples (e.g., input-x.txt and output-x.txt, x = 1, 2) are provided.
A figure corresponding input-1 can be found in this repo too.
For Python code, try the following to test your code
```
python ./solution.py < input-x.txt > my-output-x.txt
```
For C++ code, try the following to test your code
```
g++ -o mybinary solution.cpp
./mybinary < input-x.txt > my-output-x.txt
```

Your output `my-output-x.txt` needs to be *match exactly* to the given `output-x.txt`.
On Unix-based systems you can use `diff` to compare them:
```
diff my-output-x.txt output-x.txt
```
On Windows you can use `fc` to compare them:
```
fc my-output-x.txt output-x.txt
```

# Submission

If you want to upload a single file, make sure the file is named as `solution.py` (for Python) or `solution.cpp` (for C++).
If you submit via GitHub, make sure your file is located in directory `assignment3/problem1/solution.py` (for Python) or `assignment3/problem1/solution.cpp` (for C++).

# Hints

Use adjacency list to store all the edges.

Solutions

Expert Solution

First of all you want the number of connected components in directed graph G. Right?

I am assuming that you don't want the strongly connected components(which usually asked in directed graph).

Which implies that you just want the connected components in a graph G. Which is same in directed and undirected graph.

Below is the well documented code -

from collections import defaultdict

def dfs(src):
    # This is our base condition for stoping the recusrion
    # If src in taken, then it means that we've already processed it.
    if src in taken:
        return
    
    # Now we've processed src vertex so we will add it to taken set
    taken.add(src)

    # Now calling dfs for all the vertices connected to src(if any) vertex because all of them are in the same component.
    for des in adj[src]:
        dfs(des)
    
# Here n is the number of vertices and m is the total number of edges
n, m = map(int, input().split())

# Here we assigned a defaultdict(key : value[set]) object to adj
adj = defaultdict(set)

# taking all m edges
for _ in range(m):
    a, b = map(int, input().split())

    # Below line simply means there is a path from a to b
    adj[a].add(b)
    
    # Below line simply means there is a path from b to a
    adj[b].add(a)

# taken set contains all the visited vertices
taken = set()

# connected_components is the total number of connected components
connected_components = 0

# Checking from each vertices
for src in range(1, n + 1):
    # If src vertex is in taken then it means we've already consider it in a different component, hence we'll not process it this time
    if src not in taken:
        dfs(src)
        
        # For each src that is not in taken we will add 1 to connected_components, because it means src is the vertex of that component which we haven't discovered untill now.
        connected_components += 1

# Printing the total number of connected components
print(connected_components)

Time Complexity -

O(|V| + |E|), Because we are processing vertices and edges in linear time. 

Sample Input -

8 6
1 3
1 2
1 4
6 7
8 5
2 4

Sample Output -

3

Related Solutions

# Problem Description Given a directed graph G = (V, E), find the number of connected...
# Problem Description Given a directed graph G = (V, E), find the number of connected components in G. # Input The graph has `n` vertices and `m` edges. There are m + 1 lines, the first line gives two numbers `n` and `m`, describing the number of vertices and edges. Each of the following lines contains two numbers `a` and `b` meaning there is an edge (a,b) belong to E. All the numbers in a line are separated by...
# Problem Description Given a directed graph G = (V,E) with edge length l(e) > 0...
# Problem Description Given a directed graph G = (V,E) with edge length l(e) > 0 for any e in E, and a source vertex s. Use Dijkstra’s algorithm to calculate distance(s,v) for all of the vertices v in V. (You can implement your own priority queue or use the build-in function for C++/Python) # Input The graph has `n` vertices and `m` edges. There are m + 1 lines, the first line gives three numbers `n`,`m` and `s`(1 <=...
A DAG is a directed graph that contains no directed cycles. Define G = (V, E)...
A DAG is a directed graph that contains no directed cycles. Define G = (V, E) in which V is the set of all nodes as {v1, v2, ..., vi , ...vn} and E is the set of edges E = {ei,j = (vi , vj ) | vi , vj ∈ V} . A topological order of a directed graph G = (V, E) is an ordering of its nodes as {v1, v2, ..., vi , ...vn} so that...
Let G = (V, E) be a directed graph, with source s ∈ V, sink t...
Let G = (V, E) be a directed graph, with source s ∈ V, sink t ∈ V, and nonnegative edge capacities {ce}. Give a polynomial-time algorithm to decide whether G has a unique minimum s-t cut (i.e., an s-t of capacity strictly less than that of all other s-t cuts).
You are given a directed graph G(V,E) with n vertices and m edges. Let S be...
You are given a directed graph G(V,E) with n vertices and m edges. Let S be the subset of vertices in G that are able to reach some cycle in G. Design an O(n + m) time algorithm to compute the set S. You can assume that G is given to you in the adjacency-list representation.
. Provide a weighted directed graph G = (V, E, c) that includes three vertices a,...
. Provide a weighted directed graph G = (V, E, c) that includes three vertices a, b, and c, and for which the maximum-cost simple path P from a to b includes vertex c, but the subpath from a to c is not the maximum-cost path from a to c
Let G = (V, E) be a directed acyclic graph modeling a communication network. Each link...
Let G = (V, E) be a directed acyclic graph modeling a communication network. Each link e in E is associated with two parameters, w(e) and d(e), where w(e) is a non-negative number representing the cost of sending a unit-sized packet through e, and d(e) is an integer between 1 and D representing the time (or delay) needed for transmitting a packet through e. Design an algorithm to find a route for sending a packet between a given pair of...
If G = (V, E) is a graph and x ∈ V , let G \...
If G = (V, E) is a graph and x ∈ V , let G \ x be the graph whose vertex set is V \ {x} and whose edges are those edges of G that don’t contain x. Show that every connected finite graph G = (V, E) with at least two vertices has at least two vertices x1, x2 ∈ V such that G \ xi is connected.
Determine, for a given graph G =V,E and a positive integer m ≤ |V |, whether...
Determine, for a given graph G =V,E and a positive integer m ≤ |V |, whether G contains a clique of size m or more. (A clique of size k in a graph is its complete subgraph of k vertices.) Determine, for a given graph G = V,E and a positive integer m ≤ |V |, whether there is a vertex cover of size m or less for G. (A vertex cover of size k for a graph G =...
You are given an undirected graph G = ( V, E ) in which the edge...
You are given an undirected graph G = ( V, E ) in which the edge weights are highly restricted. In particular, each edge has a positive integer weight from 1 to W, where W is a constant (independent of the number of edges or vertices). Show that it is possible to compute the single-source shortest paths in such a graph in O(E+V) time.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT