Sequence Land, INOI 2013

Problem Description

Question : Sequence Land, INOI 2013

Submit Code : Codechef

Prerequisites

Depth-First Search, Connected Graph

Solution

It's clear that extended family forms a tree. The Presindent will be root node and his relatives will be its children nodes and relatives of relatives will be children nodes of them and so on.

To get our answer we will do the followings:

1. we will connect node a with node b if number of common ids will be greater than or equal to k.
2. Now, we just have to find number of nodes connected to node 0 (The President). We will use DFS to traverse all element connected with node 0.

Code

#include<bits/stdc++.h>

using namespace std;

void dfs(vector<int>* adj, vector<int>& visited, int idx){
    visited[idx] = 1;
    for(int u : adj[idx])
        if(!visited[u])
            dfs(adj, visited, u);
}

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> sequenceId[n];
    int m, x;
    
    for(int i=0;i<n;i++){
        cin >> m;
        for(int j=0;j<m;j++){
            cin >> x;
            sequenceId[i].push_back(x);
        }
    }

    vector<int> adj[n];
    for(int i=0;i<n;i++){
        map<int, int> id;
        for(int j=0;j<(int)sequenceId[i].size();j++)
            id[sequenceId[i][j]] = 1;
        for(int j=i+1;j<n;j++){
            int numCommonElement = 0;
            for(int k=0;k<(int)sequenceId[j].size();k++)
                if(id.count(sequenceId[j][k]))
                    numCommonElement++;
            if(numCommonElement >= k){
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }

    vector<int> visited(n, 0);
    dfs(adj, visited, 0);

    int extendedFamily = 0;
    for(int i=0;i<n;i++)
        if(visited[i])
            extendedFamily++;
    cout << extendedFamily;
    return 0;
}