UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#201678#3508. 朋友CheZiHe929100571ms18432kbC++111.4kb2024-02-04 11:29:112024-02-04 12:08:02

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=1e6+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: 1196kb

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: 1196kb

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: 1192kb

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: 152ms
memory: 18388kb

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: 154ms
memory: 18412kb

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: 136ms
memory: 18420kb

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: 129ms
memory: 18432kb

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