Advertisement
Guest User

Untitled

a guest
Dec 5th, 2014
258
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.88 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. int n, k;
  8. vector<int> id[305];
  9.  
  10. bool seen[305] = { };
  11. void dfs(int v)
  12. {
  13.     seen[v] = true;
  14.     for(int i = 1; i <= n; i++)
  15.     {
  16.         if(!seen[i])
  17.         {
  18.             int l = 0, r = 0, common = 0;
  19.             while(l < id[v].size() && r < id[i].size())
  20.             {
  21.                 if(id[v][l] == id[i][r])
  22.                 {
  23.                     l++;
  24.                     r++;
  25.                     common++;
  26.                     if(common == k)
  27.                     {
  28.                         dfs(i);
  29.                         break;
  30.                     }
  31.                 }
  32.                 else if(id[v][l] > id[i][r])
  33.                 {
  34.                     r++;
  35.                 }
  36.                 else
  37.                 {
  38.                     l++;
  39.                 }
  40.             }
  41.         }
  42.     }
  43. }
  44.  
  45. int main()
  46. {
  47.     cin >> n >> k;
  48.  
  49.     for(int i = 1; i <= n; i++)
  50.     {
  51.         int p;
  52.         cin >> p;
  53.         for(int j = 0; j < p; j++)
  54.         {
  55.             int x;
  56.             cin >> x;
  57.             id[i].push_back(x);
  58.         }
  59.         sort(id[i].begin(), id[i].end());
  60.     }
  61.  
  62.     dfs(1);
  63.  
  64.     int ans = 0;
  65.     for(int i = 1; i <= n; i++) if(seen[i]) ans++;
  66.     cout << ans;
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement