https://codeforces.com/contest/2044/problem/G1
https://codeforces.com/contest/2044/problem/G2
出度为1,因此是个内向基环树。模拟一下发现所有权值进入环中时,就稳定下来。
因为每个点多于1时只会保留1,所以找出挂在环上的最长链即可。然后根据定义,答案是链长度+2。
G2,模拟发现,同样是所有权值进入环中。但是由于会保留大于1的权值。再模拟一下发现,是挂在环上的树的点权和即点的数量,求出最大的点的数量,+2即可。
联想到之前做过的,内向基环树做拓扑排序,环上的点不入队。利用这个性质,这两题很好写。
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
#define MULTI_TEST
void solve(){
int n;
cin>>n;
vector<int> d(n+1);
vector<int> r(n+1);
for(int i=1;i<=n;i++){
cin>>r[i];
d[r[i]] ++;
}
int ans = 0;
queue<int> q;
vector<int> cnt(n+1,1);
for(int i=1;i<=n;i++){
if(d[i]==0){
q.push(i);
cnt[i] =1;
}
}
while(q.size()){
auto u = q.front(); q.pop();
ans = max(ans,cnt[u]);
int nxt = r[u];
d[nxt]--;
cnt[nxt] += cnt[u];
if(d[nxt]==0){
q.push(nxt);
}
}
cout<<ans+2<<endl;
}
int main(){
ifstream test_file("0in.txt");
if (test_file) {
freopen("0in.txt", "r", stdin);
freopen("0output.txt", "w", stdout);
}
std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);
int T = 1;
#ifdef MULTI_TEST
cin>>T;
#endif
while(T--){
solve();
}
return 0;
}
G2
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
#define MULTI_TEST
void solve(){
int n;
cin>>n;
vector<int> d(n+1);
vector<int> r(n+1);
for(int i=1;i<=n;i++){
cin>>r[i];
d[r[i]] ++;
}
int ans = 0;
queue<int> q;
vector<int> cnt(n+1,1);
for(int i=1;i<=n;i++){
if(d[i]==0){
q.push(i);
cnt[i] =1;
}
}
while(q.size()){
auto u = q.front(); q.pop();
ans = max(ans,cnt[u]);
int nxt = r[u];
d[nxt]--;
cnt[nxt] += cnt[u];
if(d[nxt]==0){
q.push(nxt);
}
}
cout<<ans+2<<endl;
}
int main(){
ifstream test_file("0in.txt");
if (test_file) {
freopen("0in.txt", "r", stdin);
freopen("0output.txt", "w", stdout);
}
std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);
int T = 1;
#ifdef MULTI_TEST
cin>>T;
#endif
while(T--){
solve();
}
return 0;
}