deushiro

Untitled

Dec 28th, 2019
227
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.46 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. vector <vector<int>> g;
  8. int index = 1;
  9. int n;
  10. vector<bool> flag;
  11. int counter = 0;
  12. vector<int> a;
  13. int ans = 0;
  14.  
  15. void getline(int i, string &s) {
  16.     int j = 0;
  17.     while (s[index] != ']') {
  18.         if (isdigit(s[index])) {
  19.             if (s[index] == '1')
  20.                 g[i].push_back(j);
  21.             j++;
  22.         }
  23.  
  24.         index++;
  25.     }
  26. }
  27.  
  28. void getvec(string &s, int n) {
  29.  
  30.     for (int i = 0; i < n; i++) {
  31.         getline(i, s);
  32.         index += 3;
  33.     }
  34. }
  35.  
  36. int getlen(string &s) {
  37.  
  38.     int n = 0;
  39.     int ind = 1;
  40.     while (s[ind] != ']') {
  41.         if (isdigit(s[ind]))
  42.             ++n;
  43.         ind++;
  44.  
  45.     }
  46.  
  47.     return n;
  48.  
  49. }
  50.  
  51. void dfs(int v){
  52.     flag[v] = true;
  53.     ++counter;
  54.     for(int u : g[v]){
  55.         if(!flag[u] && u != v){
  56.             dfs(u);
  57.         }
  58.     }
  59. }
  60.  
  61. int main() {
  62.     string s;
  63.     getline(cin, s);
  64.     s = s.substr(2, s.size() - 3);
  65.     int m = s[s.size() - 1] - '0';
  66.     n = getlen(s);
  67.     flag.resize(n);
  68.     g.resize(n);
  69.     s = s.substr(0, s.size() - 3);
  70.     getvec(s, n);
  71.     for (int i = 0; i < n; i++) {
  72.         if(!flag[i]){
  73.             counter = 0;
  74.             dfs(i);
  75.             if(counter == 1)
  76.                 ++ans;
  77.             else
  78.                 a.push_back(counter);
  79.         }
  80.     }
  81.     cout << endl;
  82.     for(int i = 0; i < a.size(); ++i){
  83.         cout << a[i] << " ";
  84.     }
  85. }
Advertisement
Add Comment
Please, Sign In to add comment