Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int MAX = 1e3+5;
- int t = 1, c = 0, n;
- int dfsTime[MAX], low[MAX];
- bool vis[MAX], inStack[MAX];
- stack <int> Stack;
- vector <vector <int> > adjList(MAX, vector<int>());
- int comp[MAX];
- vector <pair<int, int> > edges;
- vector<vector<int> > component;
- bool source[MAX];
- void tarjan(int node){
- vis[node] = inStack[node] = true;
- Stack.push(node);
- dfsTime[node] = low[node] = t++;
- for(int i = 0;i < (int)adjList[node].size();i++){
- if(!vis[adjList[node][i]]){
- tarjan(adjList[node][i]);
- low[node] = min(low[node], low[adjList[node][i]]);
- }
- else if(inStack[adjList[node][i]])
- low[node] = min(low[node], dfsTime[adjList[node][i]]);
- }
- if(low[node] == dfsTime[node]){
- int x = -1;
- vector <int> v;
- c++;
- while(x != node){
- x = Stack.top();
- Stack.pop();
- inStack[x] = false;
- v.push_back(x);
- comp[x] = c;
- }
- component.push_back(v);
- }
- }
- void init(){
- for(int i = 1;i <= MAX;i++) dfsTime[i] = 0;
- for(int i = 1;i <= MAX;i++) low[i] = 0;
- for(int i = 1;i <= MAX;i++) vis[i] = 0;
- for(int i = 1;i <= MAX;i++) inStack[i] = 0;
- for(int i = 1;i <= MAX;i++) comp[i] = 0;
- for(int i = 1;i <= MAX;i++) source[i] = 0;
- edges.clear();
- component.clear();
- adjList.clear();
- adjList.resize(n+5);
- while(!Stack.empty())
- Stack.pop();
- t = 1;
- c = 0;
- }
- int main() {
- int T, n, m, x, numberofSources = 0;
- cin >> T;
- while(T--){
- cin >> n;
- init();
- vector<int> b;
- b.push_back(26);
- b.push_back(8);
- component.push_back(b);
- for(int i = 1;i <= n;i++){
- cin >> m;
- while(m--){
- cin >> x;
- adjList[x].push_back(i);
- edges.push_back({x, i});
- }
- }
- for(int i = 1;i <= n;i++)
- if(!vis[i])
- tarjan(i);
- numberofSources = component.size()-1;
- for(int i = 0;i < (int)edges.size();i++){
- int u = edges[i].first;
- int v = edges[i].second;
- if(comp[u] == comp[v]) continue;
- if(!source[comp[v]])
- source[comp[v]] = true, numberofSources--;
- }
- if(numberofSources != 1)
- cout << 0 <<endl;
- else{
- int n_components = component.size() - 1;
- for(int i = 1;i <= n_components;i++){
- if(!source[i]){
- cout << component[i].size() <<endl;
- }
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment