时间限制: 1 Sec 内存限制: 128 MB
题目描述
We have N cards numbered 1 to N. Each side of each card has a color represented by a positive integer.
One side of Card i has a color ai, and the other side has a color bi.
For each card, you can choose which side shows up. Find the maximum possible number of different colors showing up.
Constraints
1≤N≤200000
1≤ai,bi≤400000
All numbers in input are integers.
输入
Input is given from Standard Input in the following format:
N
a1 b1
a2 b2
:
aN bN
输出
Print the answer.
样例输入 Copy
【样例1】 4 1 2 1 3 4 2 2 3 【样例2】 2 111 111 111 111 【样例3】 12 5 2 5 6 1 2 9 7 2 7 5 5 4 2 6 7 2 2 7 8 9 7 1 8
样例输出 Copy
【样例1】 4 【样例2】 1 【样例3】 8
提示
样例1解释
We can choose the sides with 1, 3, 4, 2 to have four colors.
样例2解释
They are painted with just one color.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,a,b;
ll ans=0,cnt=0,f=0;
vector<int>v[400005];
int flag[400005]= {0};
void dfs(int now,int fa)
{cnt++;flag[now]=1;for(int i=0; i<v[now].size(); i++){if(v[now][i]==fa)///不能倒着走continue;if(flag[v[now][i]]==0) ///不会被另一个连通图搜索dfs(v[now][i],now);else ///如果这个点被访问过，说明是环，即不是树f=1;}
}
int main()
{scanf("%d",&n);for(int i=1; i<=n; i++){scanf("%d%d",&a,&b);v[a].push_back(b);v[b].push_back(a);}for(int i=1; i<=400000; i++){if(flag[i]==0){cnt=0;f=0;dfs(i,-1);if(f) ///如果是连通图，就是全部都可以被选上ans+=cnt;else ///如果是树，就cnt-1ans+=cnt-1;}}printf("%lld",ans);
}