Below is given the code of following problem : 1907G - Lights. Can anyone explain me how the code for cyclic portion works.
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;
}
Auto comment: topic has been updated by Roronoa__Zoro (previous revision, new revision, compare).
Auto comment: topic has been updated by Roronoa__Zoro (previous revision, new revision, compare).
Auto comment: topic has been updated by Roronoa__Zoro (previous revision, new revision, compare).