codeforce每日一题链接
题目链接
题目描述
人们来到这个节日,决定跳几个圆舞,至少有两个人在跳圆舞剧,每个人正好有两个邻居。如果有两个人在圆舞剧里,那么他们的两边都有相同的邻居。你决定找出那里到底有多少支舞,但节日的每一位参加者都记得有一个邻居。你的任务是确定圆形舞蹈的最小和最大数量。例如,如果节日里有6个人,而他们记得的邻居数量相等[2,1,4,3,6,5j],那么圆舞剧的最小数量是1:1-2-3-4-5-6-1,最高为3:
样例
输入样例1
10
6
2 1 4 3 6 5
6
2 3 1 5 6 4
9
2 3 2 5 6 5 8 9 8
2
2 1
4
4 3 2 1
5
2 3 4 5 1
6
5 3 4 1 1 2
5
3 5 4 1 2
6
6 3 2 5 4 3
6
5 1 4 3 4 2
输出样例1
1 3
2 2
1 3
1 1
1 2
1 1
1 1
2 2
1 2
1 1
算法
(dfs) $O(n)$
这道题只需要深搜,判断当前连通块是环还是链就好了,最小值就是将所有的链拼接成一个环,最大值就是将所有的链自己和自己首尾相连就好。
C++ 代码
// https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 2e5 + 10, M = N * 2, INF = 0x3f3f3f3f;
int n, m;
int e[M], ne[M], h[N], idx;
bool st[N];
int in[N];
set<int> s[N];
inline void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
inline bool dfs(int u)
{
st[u] = true;
bool flag = in[u] == 2;
for(int i=h[u];~i;i=ne[i])
{
int j = e[i];
if(st[j]) continue;
flag &= dfs(j);
}
return flag;
}
inline void solve()
{
idx = 0;
memset(in, 0, sizeof in);
memset(st, 0, sizeof st);
memset(h, -1, sizeof h);
cin>>n;
for(int i=1;i<=n;i++) s[i].clear();
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
if(!s[i].count(x)){
s[i].insert(x);s[x].insert(i);
add(i, x), add(x, i);
in[i]++, in[x]++;
}
}
int cnt1 = 0, cnt2 = 0;
for(int i=1;i<=n;i++){
if(!st[i]){
if(dfs(i)) cnt1++;
else cnt2++;
}
}
// cout<<cnt1<<" "<<cnt2<<endl;
cout<<cnt1+(cnt2>0)<<" "<<cnt1+cnt2<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}