Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "stdafx.h"
- #include <iostream>
- #include <vector>
- using namespace std;
- void visit(vector<vector<int>>&, vector<bool>&, int);
- int findCircleNum(vector<vector<int>>&);
- int findCircleNum(vector<vector<int>>& M)
- {
- int ans = 0;
- vector<bool> is_visit(M.size(), 0);
- //vector<vector<int>> list;
- for (int i = 0; i < M.size(); i++)
- {
- if (is_visit[i] == false)
- {
- visit(M, is_visit, i);
- ans++;
- }
- }
- return ans;
- }
- void visit(vector<vector<int>>& M,vector<bool>& is_visit, int v)
- {
- is_visit[v] = 1;
- for (int i = 0; i < M.size(); i++)
- {
- if (M[v][i] == 1 && is_visit[i] == 0)
- {
- visit(M, is_visit, i);
- }
- }
- }
- int main()
- {
- vector < vector < int >> in1 =
- { { 1, 1, 0 },
- { 1, 1, 0 },
- { 0, 0, 1 } };
- vector < vector < int >> in2 =
- { { 1, 1, 0 },
- { 1, 1, 1 },
- { 0, 1, 1 } };
- cout << "ans is:" << findCircleNum(in1) << endl;
- cout << "ans is:" << findCircleNum(in2) << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement