Below is given the code of following problem : [problem:1907G]. Can anyone explain me how the code for cyclic portion works.↵
↵
<spoiler summary="Spoiler">↵
void solve()↵
{↵
int n ; cin >> n;↵
↵
string s ; cin >> s;↵
↵
vector<int> check(n);↵
↵
for (int i = 0 ; i < n ; i++) check[i] = (s[i] == '1');↵
↵
vector<int>a(n); input(a);↵
↵
vector<int>indegree(n);↵
↵
for (int i = 0 ; i < n ; i++)↵
↵
{↵
↵
indegree[--a[i]]++;↵
↵
}↵
↵
queue<int> q;↵
↵
vector<int> ans;↵
↵
for (int i = 0 ; i < n ; i++)↵
↵
{↵
↵
if (indegree[i] == 0)q.push(i);↵
↵
}↵
↵
while (!q.empty())↵
↵
{↵
↵
int u = q.front(); q.pop();↵
↵
if (check[u])↵
↵
{↵
↵
ans.push_back(u);↵
↵
check[u] = !check[u];↵
↵
check[a[u]] = !check[a[u]];↵
↵
}↵
↵
indegree[a[u]]--;↵
↵
if (indegree[a[u]] == 0)q.push(a[u]);↵
↵
}↵
↵
for (int i = 0 ; i < n ; i++)↵
↵
{↵
if (indegree[i])↵
↵
{↵
↵
int j = i;↵
↵
int length = 0 , track = 0 , res = 0;↵
↵
↵
while (indegree[j])↵
↵
{↵
↵
if (check[j]) track ^= 1;↵
↵
res += track;↵
↵
indegree[j] = 0;↵
↵
length++;↵
↵
j = a[j];↵
↵
}↵
↵
if (track == 1)↵
↵
{↵
↵
cout << -1 << endl;↵
↵
return;↵
↵
}↵
↵
for (int k = 0 ; k < length ; k++)↵
↵
{↵
↵
if (check[j]) track ^= 1;↵
↵
if (track == (res < length —- res))↵
↵
{↵
ans.push_back(j);↵
}↵
j = a[j];↵
}↵
}↵
}↵
cout << ans.size() << endl;↵
for (auto a : ans) cout << a + 1 << " ";↵
cout << endl;↵
}↵
</spoiler>↵
↵
↵
<spoiler summary="Spoiler">↵
void solve()↵
{↵
int n ; cin >> n;↵
↵
string s ; cin >> s;↵
↵
vector<int> check(n);↵
↵
for (int i = 0 ; i < n ; i++) check[i] = (s[i] == '1');↵
↵
vector<int>a(n); input(a);↵
↵
vector<int>indegree(n);↵
↵
for (int i = 0 ; i < n ; i++)↵
↵
{↵
↵
indegree[--a[i]]++;↵
↵
}↵
↵
queue<int> q;↵
↵
vector<int> ans;↵
↵
for (int i = 0 ; i < n ; i++)↵
↵
{↵
↵
if (indegree[i] == 0)q.push(i);↵
↵
}↵
↵
while (!q.empty())↵
↵
{↵
↵
int u = q.front(); q.pop();↵
↵
if (check[u])↵
↵
{↵
↵
ans.push_back(u);↵
↵
check[u] = !check[u];↵
↵
check[a[u]] = !check[a[u]];↵
↵
}↵
↵
indegree[a[u]]--;↵
↵
if (indegree[a[u]] == 0)q.push(a[u]);↵
↵
}↵
↵
for (int i = 0 ; i < n ; i++)↵
↵
{↵
if (indegree[i])↵
↵
{↵
↵
int j = i;↵
↵
int length = 0 , track = 0 , res = 0;↵
↵
↵
while (indegree[j])↵
↵
{↵
↵
if (check[j]) track ^= 1;↵
↵
res += track;↵
↵
indegree[j] = 0;↵
↵
length++;↵
↵
j = a[j];↵
↵
}↵
↵
if (track == 1)↵
↵
{↵
↵
cout << -1 << endl;↵
↵
return;↵
↵
}↵
↵
for (int k = 0 ; k < length ; k++)↵
↵
{↵
↵
if (check[j]) track ^= 1;↵
↵
if (track == (res < length
↵
{↵
ans.push_back(j);↵
}↵
j = a[j];↵
}↵
}↵
}↵
cout << ans.size() << endl;↵
for (auto a : ans) cout << a + 1 << " ";↵
cout << endl;↵
}↵
</spoiler>↵
↵
