圆圈舞问题分析与解答

问题描述

奶牛们围成一圈表演圆圈舞，每头奶牛通过顺时针方向的绳子连接。成功的表演要求：任意奶牛的顺时针或逆时针拉动必须能带动整个群体同步运动。绳子只能拉动不能推动，因此群体必须形成强连通分量（SCC），且每个奶牛在该分量中入度和出度均至少为1（即每个节点在分量中存在至少一个前驱和后继）。

问题分析

1. 强连通分量（SCC）的性质
   强连通分量中任意两点可相互到达。若一个群体是成功的圆圈舞群体，则其对应的子图必须是一个强连通分量，且每个节点的入度和出度均≥1。

   • 对于单个节点的分量，无法满足“左右蹄各握至少一根绳子”的条件，因此直接排除。
   • 对于大小≥2的强连通分量，若每个节点的入度和出度均≥1，则该分量满足条件。但实际上，在强连通分量中，若分量大小≥2且是强连通的，则每个节点的入度和出度必然≥1（否则无法形成强连通）。因此，只需统计大小≥2的强连通分量的数量。

2. 算法选择
   使用Tarjan算法求解有向图的强连通分量。Tarjan算法通过深度优先搜索（DFS）遍历图，利用栈和时间戳标记节点，将每个强连通分量识别为一个子图。

解决代码

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<stack>
#include<queue>
#include<map>
#include<set> 
#include<algorithm>
using namespace std;
#define lowbit(x) (x&-x)
#define mem(a,b) memset(a,b,sizeof(a))
#define eps 1e-9
#define INF 999999
#define MAXN 100000+5
//struct edge{
//	int to;
//	//int val;
//};
//int next[MAXN]; 
vector<int> G[MAXN];
int dfn[MAXN],low[MAXN];
bool instack[MAXN];
stack<int> s;				
int timing;				//时间戳 
int color[MAXN];		//代表当前结点所属第几个scc 
int colorcnt[MAXN];		//代表第某个scc有几个结点 
int cnt;				//scc个数 
int V,E;				
 
void init()
{
	for(int i=0;i<=V;i++)
		G[i].clear();
	while(!s.empty())
		s.pop();
	mem(dfn,0);
	mem(color,0);
	mem(colorcnt,0);
	mem(instack,false);
	mem(low,0);
	timing=cnt=0;
}
 
void tarjan(int u)
{
	timing++;
	dfn[u]=low[u]=timing;
	s.push(u);
	instack[u]=true;
	for(int i=0;i<G[u].size();i++)
	{
		int v=G[u][i];
		if(dfn[v]==0)
		{	
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(instack[v])
		{
			low[u]=min(low[u],dfn[v]);
		}
	}
	
	if(low[u]==dfn[u])
	{
		cnt++;
		int temp;
		do
		{
			//记录每个点属于哪个scc
			temp=s.top();
			s.pop();
			instack[temp]=false;
			color[temp]=cnt;
			colorcnt[cnt]++;	
		}while(u!=temp);	
	}
}
 
int main()
{
	ios::sync_with_stdio(false);
	while(cin >> V >> E && V+E)
	{
		init();
		int a,b,maxn=(-INF);
		for(int i=0;i<E;i++)
		{
			cin >> a >> b;
			G[a].push_back(b);
			maxn=max(maxn,a);
			maxn=max(maxn,b);
		}
		for(int i=1;i<=V;i++)
			if(dfn[i]==0)
				tarjan(i);
		int ans=0;
			for(int i=1;i<=cnt;i++)
				if(colorcnt[i]>1)
					ans++;
			cout << ans << endl;
					
	}
	return 0;
}

代码解释

1. 数据结构

   • 使用邻接表G存储有向图，G[a]保存从奶牛a出发的所有顺时针绳子连接的奶牛。
   • dfn和low数组用于Tarjan算法记录时间戳和回溯点。
   • color数组记录每个节点所属的强连通分量编号，colorcnt统计每个分量的节点数。

2. Tarjan算法

   • 从每个未访问的节点出发进行DFS，利用栈维护当前路径上的节点。
   • 当发现某个节点的low值等于其dfn值时，说明找到一个强连通分量的根节点，弹出栈中节点直到根节点，标记所属分量并统计大小。

3. 结果统计
   遍历所有强连通分量，统计节点数≥2的分量数量，即为满足条件的圆圈舞群体数量。

关键点

• 强连通分量的性质保证了群体的双向拉动能力。
• 单个节点无法满足条件，只需判断分量大小是否≥2。
• Tarjan算法高效求解强连通分量，时间复杂度为O(N+M)，适用于题目数据规模。