1 条题解
-
1
大家好,我是 CQ-C2024 蒟蒻 CJH。
洛谷博客。
题意
题目描述写得很清楚了。标签:并查集。
分析题目
此题就是一道近似于模板的一道并查集的题。
在这里我用 表示 是属于哪一队的,用 表示 的敌队。
在 次比赛中,需要判断 和 是否为相同的队伍,如果是就直接输出此场比赛 。
否则当 的敌队不为初始状态时,合并 和 ;同样再对 和 执行此操作。
代码实现
//the code is from chenjh #include<cstdio> #define MAXN 100001 using namespace std; int fa[MAXN],d[MAXN]; inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);} void merge(int x,int y){fa[x]=y;} int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) fa[i]=i;//初始化 fa 数组。 for(int t=1,x,y;t<=m;t++){ scanf("%d%d",&x,&y); int rx=find(x),ry=find(y);//获得两队队伍。 if(rx==ry) return printf("%d\n",t),0;//如果两队队伍相同则输出并结束程序。 if(d[x] && find(d[x])!=ry) merge(find(d[x]),ry);//合并 if(d[y] && find(d[y])!=rx) merge(find(d[y]),rx); d[x]=ry,d[y]=rx;//记录敌队 } return 0; }
谢谢大家!
- 1
信息
- ID
- 7108
- 时间
- 1000ms
- 内存
- 32MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者