277a.cpp
unknown
c_cpp
a year ago
1.4 kB
6
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;
}Editor is loading...
Leave a Comment