NC15906. Jump
描述
The new version of Lianliankan is a game you love to play with. The rules of the game are as follows:
Give you n boxes, each with its own properties, two integers x, y. (1≤x,y≤10000)
You can only start from the box with property 1 then connect the next boxes which has property 2 and so on.The properties of boxes you have chosen are increased.
Each box can only be selected once.When you choose the box,you can only use the one property of it.
In other words, you can only select a box with property 1 at first, then connect to a box with property 2, and then connect to a box with property 3.......
How many boxes can you connect ?(The more the better.ass we can)
输入描述
The first line is one integer n(1≤n≤1000000)
Then n lines follow,each line contains two integers,which are the box‘s properties
Using fast I/O to avoid Time-Limit-Exceeded
输出描述
Output the answer we want
示例1
输入:
4 1 2 2 4 2 3 2 5
输出:
4
说明:
choose 1 of box 1 ,2 of box 4,3 of box 3,4 of box 2示例2
输入:
4 1 2 1 2 2 3 1 2
输出:
3
说明:
choose 1 of box 1 ，2 of box 2 and 3 of box 3C++(clang++ 11.0.1) 解法, 执行用时: 413ms, 内存消耗: 39544K, 提交时间: 2023-04-07 19:53:28
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+9;
int n;
int home[N];
bool vis[N];
int find(int x)
{
if(home[x]==x) return x;
return home[x]=find(home[x]);
}
void add(int a,int b)
{
a=find(a);
b=find(b);
if(a<b) home[a]=b;
else home[b]=a;
}
int main(void)
{
for(int i=1;i<=N;i++) home[i]=i;
cin>>n;
for(int i=1;i<=n;i++){
int a,b;
cin>>a>>b;
add(a,b);
vis[a]=vis[b]=1;
}
int ans=0;
for(int i=1;i<=N;i++){
if(vis[i]) ans++;
else break;
}
cout<<ans;
}
C++14(g++5.4) 解法, 执行用时: 257ms, 内存消耗: 480K, 提交时间: 2018-05-28 15:35:11
#include<cstdio>
const int N=1e4+88;
bool vis[N];
int fa[N];
int findx(int x){
return x==fa[x]?x:(fa[x]=findx(fa[x]));
}
int main(){
int n,x,y;
for(int i=1;i<=10000;++i) fa[i]=i;
for(scanf("%d",&n);n--;){
scanf("%d%d",&x,&y);
int fx=findx(x),fy=findx(y);
if(fx>fy) fx^=fy,fy^=fx,fx^=fy;
if(fx==fy) vis[fx]=1;
else {
fa[fx]=fy;
if(vis[fx]||vis[fy]) vis[fy]=1;
vis[fx]=1;
}
}
int ans=0;
for(int i=1;i<=10000;++i) if(vis[i]) ++ans;else break;
printf("%d\n",ans);
}