首页 > 其他分享 >CF-25D - Roads not only in Berland(并查集或者搜索)

CF-25D - Roads not only in Berland(并查集或者搜索)

时间:2023-02-24 10:33:01浏览次数:63  
标签:cities Berland int 查集 CF countries find road



D - Roads not only in Berland

Crawling in process...

Crawling failed

Time Limit:2000MSMemory Limit:262144KB64bit IO Format:%I64d & %I64u


​Submit​​​ ​​​Status​​​ ​​​Practice​​​ ​​​CodeForces 25D​


Description



Berland Government decided to improve relations with neighboring countries. First of all, it was decided to build new roads so that from each city of Berland and neighboring countries it became possible to reach all the others. There aren cities in Berland and neighboring countries in total and exactlyn - 1


Input



The first line contains integer n (2 ≤ n ≤ 1000) — amount of cities in Berland and neighboring countries. Nextn - 1 lines contain the description of roads. Each road is described by two space-separated integersai,bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — pair of cities, which the road connects. It can't be more than one road between a pair of cities. No road connects the city with itself.



Output



Output the answer, number t — what is the least amount of days needed to rebuild roads so that from each city it became possible to reach all the others. Then outputt lines — the plan of closure of old roads and building of new ones. Each line should describe one day in the formati j u v — it means that road between citiesi andj became closed and a new road between citiesu andv



Sample Input



Input

2
1 2



Output


0


Input

7
1 2
2 3
3 1
4 5
5 6
6 7


Output



1 3 1 3 7



思路1:最早的思路是搜索,每次递归传递当前的点,和它的父节点,而后它的子节点不能为父节点,这样搜到已经搜过的点就说明有环,那就去点这条边,搜下没搜过的点,把边连过去,这样就OK了。

思路2:用并查集,每次找读入两个点的根,如果根一样则说明有环,记录这条边,如果根不一样就合并,因为当前两点是相连的。

             然后遍历一遍,有几个集合,就需要改几条边,每次从环里删条边就连接两集合。

失误:不知道怎么回事,用搜索老是乱整内存,意外终止,调不清楚,vector使用的时候也出很大问题,为什么it!=mp[u].end();它不终止而报错

           耽误了好长时间调试,最后才用并查集搞定了。

#include <stdio.h>
#include <vector>
using namespace std;

int f[1005];
int find(int x)
{
return f[x]==x?f[x]:f[x]=find(f[x]);
}
void he(int x, int y)
{
f[find(x)]=find(y);
}

int main(void)
{
int n, i;
scanf("%d", &n);
for(i=1;i<=n;i++)
f[i] = i;
vector<pair<int, int> > p;
vector<int> q;
for(i=1;i<n;i++)
{
int x, y;
scanf("%d%d", &x, &y);
if(find(x)==find(y))
p.push_back(make_pair(x, y));///有环记录这条边,待会删去
else he(x, y);
}
for(i=1;i<=n;i++)///找有几个不同集合,就需要改几调边
if(find(i)==i) q.push_back(i);
printf("%d\n", q.size()-1);
for(i=1;i<(int)q.size();i++)///去个环,合并两个集合
printf("%d %d %d %d\n", p[i-1].first, p[i-1].second, q[i-1], q[i]);
return 0;
}





标签:cities,Berland,int,查集,CF,countries,find,road
From: https://blog.51cto.com/u_15953788/6082910

相关文章

  • CF737E Tanya is 5!
    全在口胡,没写代码首先不考虑复制。显然是一个二分图匹配问题。如果能分成\(k\)次若干组匹配,那么答案一定不超过\(k\)。建出二分图,答案有下界:最大的度数。想象一下,每......
  • 可持久化并查集
    本文因为做题做颓废了于是上B站学了下这玩意只因本概念支持回退,访问之前版本。建立在可持久化数组上。把fa数组可持久化并查集优化路径压缩按秩合并因为fa......
  • CF611H New Year and Forgotten Tree
    首先注意到:任何合法方案一定能调整成:每种位数选一个关键点,每条边都至少有一个关键点。本质上是希望找一个边和点的匹配。一种思路是确定关键点之间形成的树后(暴力枚举),让......
  • CF245H Queries for Number of Palindromes
    对字符串s,多次询问,给你两个数L和R,问在字符串区间l到r的字串中,包含多少回文串。 #include<iostream>#include<queue>#include<cstring>#defineIOSstd::ios::syn......
  • 【五期邹昱夫】CCF-A(ICCV'21)On the Difficulty of Membership Inference Attacks
    "Rezaei,Shahbaz,andXinLiu."Onthedifficultyofmembershipinferenceattacks."ProceedingsoftheIEEE/CVFConferenceonComputerVisionandPatternRec......
  • CF818G - Four Melody
    题意:对于一个序列,令一个\(melody\)为一个子序列满足子序列的相邻两项相差\(1\)或者模\(7\)同余。现在提取四个不重合的\(melody\),求最长总长度。我们先考虑暴力的......
  • CF818F - Level Generation
    题意:假设当前有\(n\)个点,求最多的边数,使得桥的数量\(\ge\lceil\dfrac{m}{2}\rceil\)。我们考虑构造,首先,整张图一共只有一个双连通分量。因为我们如果有两个双连通分量,......
  • CF825G - Tree Queries
    现在有\(n\)次操作,每次将一个点设为黑色,或者查询:从当前点到任意黑点路径上最小值的最小值。保证第一次操作是设置黑点。强制在线。我们考虑这样一个过程,我们把第一次操......
  • CF825F - String Compression
    题意:压缩字符串,把字符串分成若干个子串,每个子串可以被压缩成“循环次数\(+\)循环节”的形式,求最小长度。dp求lcp先\(O(n^2)\)dp求出所有后缀对的\(lcp_{x,y}\),(也......
  • CF845G - Shortest Path Problem?
    题意:求带边权无向图上\(1\)到\(n\)的异或最短路,可以重复经过某条边。首先,我们考虑从\(x\)到\(y\)的路径\(A\),它的权值是\(a\)。我们从路径中途的某个地方离开路......