ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#201676 | #3508. 朋友 | CheZiHe929 | 100 | 677ms | 18420kb | C++11 | 1.4kb | 2024-02-04 11:28:10 | 2024-02-04 12:26:58 |
answer
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define debug puts("#CheZiHe929")
#define Yes puts("Yes")
#define No puts("No")
const int MAXN=1e5+5;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;}
inline void print(int x){char st[105];int top=0;if(x==0)putchar('0');if(x<0)putchar('-');while(x){if(x>0)st[++top]=x%10+48;else st[++top]=-(x%10)+48;x/=10;}while(top)putchar(st[top--]);}
inline void println(int x){print(x);putchar('\n');}
inline void printsp(int x){print(x);putchar(' ');}
inline void put(int x,int i,int n){i==n?println(x):printsp(x);}
int n,a[MAXN],b[MAXN];
int ans[MAXN],anss,fa[MAXN];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x,int y){
int fx=find(x),fy=find(y);
if(fx!=fy)fa[fx]=fy;
}
std::map<int,std::vector<int> > v;
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n=read();
for(int i=1;i<=n;i++){
a[i]=read(),b[i]=read();
fa[i]=i;
v[a[i]].push_back(i);
if(a[i]!=b[i])
v[b[i]].push_back(i);
}
for(auto p:v){
std::vector<int> x=p.second;
for(int i=1;i<x.size();i++)merge(x[0],x[i]);
}
for(int i=1;i<=n;i++)ans[find(i)]++;
for(int i=1;i<=n;i++)anss+=ans[i]/2;
put(anss,1,1);
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1200kb
input:
10 19 12 8 18 6 15 4 18 15 3 8 2 6 18 18 7 18 3 8 3
output:
4
result:
ok single line: '4'
Test #2:
score: 10
Accepted
time: 0ms
memory: 1196kb
input:
10 19 16 14 8 8 12 7 10 15 5 7 10 17 7 5 4 9 6 6 12
output:
4
result:
ok single line: '4'
Test #3:
score: 10
Accepted
time: 0ms
memory: 1200kb
input:
10 7 17 11 9 18 5 11 14 10 11 7 18 11 9 4 1 3 16 8 17
output:
4
result:
ok single line: '4'
Test #4:
score: 10
Accepted
time: 0ms
memory: 1196kb
input:
20 11 1 29 27 11 34 10 27 9 10 10 21 17 18 19 14 26 14 6 26 38 30 40 11 13 7 33 9 10 32 40 28 20 21 ...
output:
7
result:
ok single line: '7'
Test #5:
score: 10
Accepted
time: 0ms
memory: 1192kb
input:
20 19 21 15 9 33 10 9 15 5 32 10 21 28 19 22 11 20 4 32 10 26 8 13 27 30 7 11 22 2 35 8 14 17 28 9 3...
output:
7
result:
ok single line: '7'
Test #6:
score: 10
Accepted
time: 0ms
memory: 1200kb
input:
20 19 10 8 14 6 27 24 19 40 38 17 29 30 28 33 8 23 26 10 11 7 34 2 26 35 3 3 28 20 17 35 30 30 36 18...
output:
7
result:
ok single line: '7'
Test #7:
score: 10
Accepted
time: 135ms
memory: 18380kb
input:
100000 92387 35422 124898 132532 192988 84636 99872 57831 131700 147597 179017 125316 96560 4822 318...
output:
40939
result:
ok single line: '40939'
Test #8:
score: 10
Accepted
time: 180ms
memory: 18400kb
input:
100000 8515 151563 105451 194713 109537 130709 63343 41819 65855 51779 39457 85060 96650 174359 1936...
output:
40841
result:
ok single line: '40841'
Test #9:
score: 10
Accepted
time: 181ms
memory: 18408kb
input:
100000 91939 100407 110197 24191 58791 9486 68030 25807 11 188665 132600 12100 129445 33496 196658 1...
output:
40820
result:
ok single line: '40820'
Test #10:
score: 10
Accepted
time: 181ms
memory: 18420kb
input:
100000 30518 196518 74071 159971 150121 4862 43967 173607 19138 90754 19513 171337 183499 149873 142...
output:
40816
result:
ok single line: '40816'
Extra Test:
score: 0
Extra Test Passed