277a.cpp

 avatar
unknown
c_cpp
14 days ago
1.4 kB
2
Indexable
#include<bits/stdc++.h>
using namespace std;


int main() {
    int n, m;
    cin >> n >> m;
    vector<list<int>> ptol(n); // person to langua for input
    int zeroPerson = 0;
    for (int i = 0; i < n;i++){
        int totalLan;
        cin >> totalLan;
        if(totalLan == 0)
            zeroPerson++;
        while(totalLan--){
            int el;
            cin >> el;
            ptol[i].push_back(el);
        }
    }

    unordered_map<int, list<int>> g; // language to person for graph (person as nodes)
    for (int i = 0; i<n; i++){
        for(int it:ptol[i]){
            g[it].push_back(i);
        }
    }

    vector<bool> visited(n, false);
    
    function<void(int)> dfs = [&](int node) {
        visited[node] = true;
        for (int lang : ptol[node]) {
            for (int nbr : g[lang]) {
                if (!visited[nbr]) {
                    dfs(nbr);
                }
            }
        }
    };

    int connectedComponents = 0;
    
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i);
            connectedComponents++;
        }
    }
    if(zeroPerson == n){
        // connectedComponents = (connectedComponents - zeroPerson - 1);
        cout << n << endl;
    }
    else
        cout << connectedComponents - 1 << endl;
}
Leave a Comment