fork download
copy 
  1. #include<iostream>
  2. #include<map>
  3. #include<vector>
  4. #include<queue>
  5. #include<string>
  6. #include<set>
  7.  
  8. std::map<int, std::vector<int>*> adjList;
  9.  
  10. int edgeCnt;
  11. int vtxCnt;
  12.  
  13. std::vector<int> visited; 
  14. std::queue<int> queue;
  15.  
  16. std::set<int> looper;
  17.  
  18. int isolated = 0;//고립된 연결요소의 개수
  19.  
  20. auto contains(std::vector<int> v, int integer)
  21. -> bool
  22. {
  23. 	int size = v.size();
  24. 	for(int i = 0; i < size; ++i){ if(v.at(i) == integer){ return true; } }
  25. 	return false;
  26. }
  27.  
  28. void bfs(){
  29. 	if(queue.empty()){++isolated; return;}
  30. 	auto qSize = queue.size();
  31. 	for(int i = 0; i < qSize; ++i){
  32. 		int val = queue.front();
  33. 		auto toList = adjList[val];
  34. 		int tlSize = toList->size();
  35. 		for(int j = 0; j < tlSize; ++j){
  36. 			auto to = toList->at(j);
  37. 			if(contains(visited, to)){continue;}
  38. 			visited.emplace_back(to);
  39. 			queue.push(to);
  40. 		}
  41. 		queue.pop();
  42. 	}
  43. 	bfs();
  44. }
  45.  
  46. int main(){
  47.  
  48. 	std::cin >> vtxCnt;
  49. 	std::cin >> edgeCnt;
  50.  
  51. 	if(vtxCnt == 1){ std::cout << "1" << std::endl; return 0; }
  52.  
  53. 	for(int i = 0; i < edgeCnt; ++i){
  54. 		int from = 0;
  55. 		int to = 0;
  56. 		std::cin >> from;
  57. 		std::cin >> to;
  58.  
  59. 		//Key가 존재하지 않을 경우(from -> to)
  60. 		if(adjList.end() == adjList.find(from)){
  61. 			std::vector<int>* v = new std::vector<int>;
  62. 			adjList.insert(std::make_pair(from, v));
  63. 		}
  64. 		adjList.at(from)->emplace_back(to);
  65. 		//Key가 존재하지 않을 경우(to -> from)
  66. 		if(adjList.end() == adjList.find(to)){
  67. 			std::vector<int>* v = new std::vector<int>;
  68. 			adjList.insert(std::make_pair(to, v));
  69. 		}
  70. 		adjList.at(to)->emplace_back(from);
  71.  
  72. 		looper.insert(to);
  73. 		looper.insert(from);
  74.  
  75. 	}
  76.  
  77. 	for(auto it = looper.begin(); it != looper.end(); ++it){
  78. 			auto val = *it;
  79. 			if(contains(visited, val)){continue;}
  80. 			queue.push(val);
  81. 			visited.emplace_back(val);
  82. 			bfs();
  83. 	}
  84.  
  85. 	std::cout << isolated << std::endl;
  86.  
  87. 	/*int pause;
  88. 	std::cin >> pause;*/
  89. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
3 1
1 2
stdout
copy 
1
https://ideone.com/JFGUvg
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!