Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /// C++ program to count number of edge in undirected graph
- #include<bits/stdc++.h>
- using namespace std;
- class Graph /// Adjacency list representation of graph
- {
- int V ;
- list <int> *adj;
- public :
- Graph(int V)
- {
- this->V=V ;
- adj=new list<int>[V];
- }
- void addEdge( int u,int v);
- int countEdges() ;
- };
- void Graph::addEdge(int u,int v) /// add edge to graph
- {
- adj[u].push_back(v);
- adj[v].push_back(u);
- }
- /// Returns count of edge in undirected graph
- int Graph::countEdges()
- {
- int sum=0;
- /// traverse all vertex
- for(int i=0;i<V;++i)
- sum+=adj[i].size(); /// add all edge that are linked to the current vertex
- /// The count of edge is always even because in undirected graph every edge is connected twice between two vertices
- return sum/2;
- }
- int main()
- {
- int n,x,y,V=200001;
- Graph g(V); /// making above uhown graph
- cin>>n;
- for(int i=1;i<=n;++i)
- cin>>x>>y,g.addEdge(x,y);
- cout<<g.countEdges()/2<<'\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment