【2021年度训练联盟热身训练赛第二场】
F Interstellar Love (DFS or 并查集)
【题目描述】
After two years of sharing a bedroom with you in a college dorm, Jeff finally has his own room. Excited about inviting girls over to his room, he ponders over what decorations the fairer sex will enjoy.1 He decides upon setting up a “fake” planetarium with a black ceiling and glow in the dark stars that form constellations. Unfortunately, in his haste, he has made several “errors” in setting up his constellations. See, everyone knows that constellations don’t have cycles in them. Instead, whenever we visually connect the stars together with lines, a tree is always formed. (A cycle is formed when you can start at a star and, using connections, go to one or more other stars and then end up at the original star.)
Since you were Jeff’s roommate for two years, you figure you’ll help him fix his constellations. Your job will be twofold: to count the number of constellations Jeff has, and to report how many of them have cycles and need to be fixed. A constellation consists of multiple stars that are all connected to one another (directly or indirectly). A constellation that needs fixing is simply one that has a cycle.
The Problem:
Given several configurations of stars and connections between stars, determine how many constellations are defined in each configuration and how many need fixing.
【输入描述】
The first input line contains a positive integer, n (n ≤ 100), indicating the number of night skies to consider. The first line of each night sky contains two positive integers, s (s ≤ 1000), representing the number of stars for this night sky, and c (c ≤ 10000), representing the total number of connections between pairs of stars for this night sky. Each of the following c input lines contains two distinct positive integers representing a single connection between two stars. The stars in each test case will be numbered 1 through s, inclusive. A connection is considered bidirectional, thus, if a is connected to b, b is connected to a. Assume that all connections in a data set are distinct, i.e., no duplicates. Also assume that there will never be a connection from a star to itself.
1 This is based on a true story. The person who is the inspiration for this story did, in fact, major in Planetary Science and make his room’s ceiling a relatively accurate depiction of the night sky, as seen in Boston circa 1995.
【输出描述】
For each test case, just output a line with the following format:
Night sky #k: X constellations, of which Y need to be fixed.
where k is the number of the night sky, starting at 1, X is the total number of constellations described in that night sky, and Y is how many of those constellations contain a cycle.
Leave a blank line after the output for each test case.
样例输入
3
5 4
1 2
1 3
2 3
4 5
8 5
1 2
3 4
6 7
6 8
8 7
3 2
1 2
1 3
样例输出
Night sky #1: 2 constellations, of which 1 need to be fixed.
Night sky #2: 3 constellations, of which 1 need to be fixed.
Night sky #3: 1 constellations, of which 0 need to be fixed.
【解题思路】
这道题是一道图论问题,并不是很复杂。对于每一组样例,输入点和边的数量,以及每条边的两个结点(无向图)。答案要求输出的两个值分别为 非单个点的连通分量的数量 和 存在环的连通分量的数量。
我们可以使用DFS或者并查集来完成,下面分别给出两种解法的代码。
【AC代码】
解法1 DFS
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int num=20005;
struct edge
{
int to,next;
}edge[num];
int cnt,head[num];
void init()
{
for(int i=0;i<num;i++)
{
edge[i].next=-1;
head[i]=-1;
}
cnt=0;
}
void addedge(int u,int v)
{
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}
int vis[10005],flag;
void dfs(int x,int fa)
{
for(int i=head[x];i!=-1;i=edge[i].next)
if(edge[i].to!=fa)
{
if(vis[edge[i].to]==0)
{
vis[edge[i].to]=1;
dfs(edge[i].to,x);
}
else
flag=0;
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T;
cin>>T;
for(int t=1;t<=T;t++)
{
int n,m,a,b,ans=0,fix=0;
cin>>n>>m;
init();
memset(vis,0,sizeof(vis));
for(int i=1;i<=m;i++)
{
cin>>a>>b;
addedge(a,b);
addedge(b,a);
}
for(int i=1;i<=n;i++)
if(vis[i]==0)
{
vis[i]=1;
flag=1;
if(head[i]!=-1)
{
ans++;
dfs(i,0);
if(flag==0)
fix++;
}
}
printf("Night sky #%d: %d constellations, of which %d need to be fixed.\n\n",t,ans,fix);
}
return 0;
}
解法2 并查集
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int num=20005;
int vis[num],fanode[num],faedge[num];//点的祖先节点,边的祖先节点
int havenode[num],haveedge[num];//祖先节点连接点数,祖先节点连接边数
int find(int x)
{
return x==fanode[x]?x:fanode[x]=find(fanode[x]);
}
int main()
{
int T;
cin>>T;
for(int t=1;t<=T;t++)
{
int n,m,a,b,ans=0,fix=0;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
fanode[i]=i;
vis[i]=havenode[i]=haveedge[i]=0;
}
for(int i=1;i<=m;i++)
{
cin>>a>>b;
vis[a]=vis[b]=1;
int x=find(a),y=find(b);
if(x!=y)
fanode[x]=fanode[y];
faedge[i]=fanode[y];
}
for(int i=1;i<=n;i++)
havenode[find(fanode[i])]++;
for(int i=1;i<=m;i++)
haveedge[find(faedge[i])]++;
//for(int i=1;i<=n;i++)
// cout<<havenode[i]<<" "<<haveedge[i]<<endl;
for(int i=1;i<=n;i++)
{
if(vis[i]&&havenode[i])
{
ans++;//至少有两个结点的连通分量
if(havenode[i]<=haveedge[i])
fix++;//存在环的连通分量
}
}
printf("Night sky #%d: %d constellations, of which %d need to be fixed.\n\n",t,ans,fix);
}
return 0;
}
default.asp < html > < head > < title >星河影动之磁盘序列号加密代码存...
由于自己疏忽,导致请求错误405,然后前端数据传输没错,百度大都说跟post提交方...
前言 项目开发中不管是前台还是后台都会遇到烦人的null,数据库表中字段允许空值...
近期知晓云的版本更新通知频率低于去年,但我们的产品经理和工程师一直在努力地...
多选列表 (Multi-Select) 是一种将所有选项列出,并允许用户利用 Ctrl/Shift ...
俗话说:三句不离本行,对于程序员这个可爱的群体来说也是一样,即使面对无休无...
它不需要安装任何形式的客户端,兼容绝大多数主流浏览器,支持ASP.Net、ASP、Col...
命令简介 pstree 命令以树状图的方式展现进程之间的派生关系。 [root@centos7?~]...
3月14日消息 得益于 6GB 以上大内存的普及,目前的主流的安卓手机大都为 64 位系...
NicEdit的Javascript集成到任何网站在几秒钟内作出的任何元素/区块编辑或转换标...