a53

unghidrept

a53
Jan 15th, 2021
155
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.04 KB | None | 0 0
  1. /// C++ program to count number of edge in undirected graph
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. class Graph /// Adjacency list representation of graph
  6. {
  7. int V ;
  8. list <int> *adj;
  9. public :
  10. Graph(int V)
  11. {
  12. this->V=V ;
  13. adj=new list<int>[V];
  14. }
  15. void addEdge( int u,int v);
  16. int countEdges() ;
  17. };
  18.  
  19. void Graph::addEdge(int u,int v) /// add edge to graph
  20. {
  21. adj[u].push_back(v);
  22. adj[v].push_back(u);
  23. }
  24.  
  25. /// Returns count of edge in undirected graph
  26. int Graph::countEdges()
  27. {
  28. int sum=0;
  29. /// traverse all vertex
  30. for(int i=0;i<V;++i)
  31. sum+=adj[i].size(); /// add all edge that are linked to the current vertex
  32. /// The count of edge is always even because in undirected graph every edge is connected twice between two vertices
  33. return sum/2;
  34. }
  35.  
  36. int main()
  37. {
  38. int n,x,y,V=200001;
  39. Graph g(V); /// making above uhown graph
  40. cin>>n;
  41. for(int i=1;i<=n;++i)
  42. cin>>x>>y,g.addEdge(x,y);
  43. cout<<g.countEdges()/2<<'\n';
  44. return 0;
  45. }
  46.  
Advertisement
Add Comment
Please, Sign In to add comment