2021年度訓練聯盟熱身訓練賽第二場 F Interstellar Love DFS 并查集

【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;
}