Guest User

Untitled

a guest
Oct 1st, 2016
417
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.36 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MAX = 1e3+5;
  4. int t = 1, c = 0, n;
  5. int dfsTime[MAX], low[MAX];
  6. bool vis[MAX], inStack[MAX];
  7. stack <int> Stack;
  8. vector <vector <int> > adjList(MAX, vector<int>());
  9. int comp[MAX];
  10. vector <pair<int, int> > edges;
  11. vector<vector<int> > component;
  12. bool source[MAX];
  13. void tarjan(int node){
  14.     vis[node] = inStack[node] = true;
  15.     Stack.push(node);
  16.     dfsTime[node] = low[node] = t++;
  17.     for(int i = 0;i < (int)adjList[node].size();i++){
  18.         if(!vis[adjList[node][i]]){
  19.             tarjan(adjList[node][i]);
  20.             low[node] = min(low[node], low[adjList[node][i]]);
  21.         }
  22.         else if(inStack[adjList[node][i]])
  23.             low[node] = min(low[node], dfsTime[adjList[node][i]]);
  24.     }
  25.     if(low[node] == dfsTime[node]){
  26.        int x = -1;
  27.        vector <int> v;
  28.        c++;
  29.        while(x != node){
  30.            x = Stack.top();
  31.            Stack.pop();
  32.            inStack[x] = false;
  33.            v.push_back(x);
  34.            comp[x] = c;
  35.        }
  36.        component.push_back(v);
  37.     }
  38.  
  39. }
  40. void init(){
  41.     for(int i = 1;i <= MAX;i++) dfsTime[i] = 0;
  42.     for(int i = 1;i <= MAX;i++) low[i] = 0;
  43.     for(int i = 1;i <= MAX;i++) vis[i] = 0;
  44.     for(int i = 1;i <= MAX;i++) inStack[i] = 0;
  45.     for(int i = 1;i <= MAX;i++) comp[i] = 0;
  46.     for(int i = 1;i <= MAX;i++) source[i] = 0;
  47.     edges.clear();
  48.     component.clear();
  49.     adjList.clear();
  50.     adjList.resize(n+5);
  51.     while(!Stack.empty())
  52.         Stack.pop();
  53.     t = 1;
  54.     c = 0;
  55.  
  56.  
  57. }
  58.  
  59. int main() {
  60.     int T, n, m, x, numberofSources = 0;
  61.     cin >> T;
  62.     while(T--){
  63.  
  64.         cin >> n;
  65.         init();
  66.         vector<int> b;
  67.         b.push_back(26);
  68.         b.push_back(8);
  69.         component.push_back(b);
  70.         for(int i = 1;i <= n;i++){
  71.             cin >> m;
  72.             while(m--){
  73.                 cin >> x;
  74.                 adjList[x].push_back(i);
  75.                 edges.push_back({x, i});
  76.             }
  77.         }
  78.         for(int i = 1;i <= n;i++)
  79.             if(!vis[i])
  80.                 tarjan(i);
  81.  
  82.         numberofSources = component.size()-1;
  83.         for(int i = 0;i < (int)edges.size();i++){
  84.             int u = edges[i].first;
  85.             int v = edges[i].second;
  86.  
  87.             if(comp[u] == comp[v]) continue;
  88.             if(!source[comp[v]])
  89.                 source[comp[v]] = true, numberofSources--;
  90.  
  91.         }
  92.  
  93.         if(numberofSources != 1)
  94.             cout << 0 <<endl;
  95.         else{
  96.  
  97.             int n_components = component.size() - 1;
  98.                     for(int i = 1;i <= n_components;i++){
  99.                         if(!source[i]){
  100.                             cout << component[i].size() <<endl;
  101.                         }
  102.                     }
  103.             }
  104.     }
  105.     return 0;
  106. }
Advertisement
Add Comment
Please, Sign In to add comment