Users with at Most One Distinct Correspondent
National Olympiad — National round (2014 season)
Submission name: letters.cpp
Problem summary
Count users who exchanged messages with at most one other distinct person. Either message direction creates a relation, and repetitions do not create additional partners.
Input
n m followed by m sender-recipient pairs.
Output
The number of qualifying users.
Constraints
1 ≤ n ≤ 100000; 0 ≤ m ≤ 100000; labels 1…n.
Worked example
Input and output for the worked example discussed below.
Input
6 5 1 2 2 1 2 4 3 5 4 3
Output
3
Solution analysis
- A full neighbour set is unnecessary for a threshold of one. Store the first distinct partner of each user and a flag recording whether any different partner has appeared.
- Update both endpoints for each message, ignoring self-messages because the statement concerns another person. Repeated or reciprocal records of the same pair leave the flag unchanged.
- In the sample users 1 and 5 each have one partner and user 6 has none. The remaining users have at least two, so output 3. Once the flag becomes true, later messages cannot restore eligibility.
Why it works
The first-partner entry remembers the only possible unique partner; encountering another distinct label proves there are at least two. Thus the flag is true exactly for users that must be excluded, and counting false flags gives the answer.
Watch out. Ignore direction when counting correspondence. Repeated messages are not new people; self-messages are not another person. Isolated users qualify.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int users;
int messages;
cin>>users>>messages;
vector<int>first(users+1);
vector<bool>multiple(users+1);
auto add=[&](int user,int partner){
if(user==partner){
return;
}
if(first[user]==0){
first[user]=partner;
}
else if(first[user]!=partner){
multiple[user]=true;
}
};
for(int i=0;i<messages;i++){
int a;
int b;
cin>>a>>b;
// Correspondence counts at both endpoints regardless of direction.
add(a,b);
add(b,a);
}
int answer=0;
for(int user=1;user<=users;user++){
if(!multiple[user]){
answer++;
}
}
cout<<answer<<'\n';
}