277a.cpp
#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