Help in understanding code !!!
Разница между en4 и en5, 1 символ(ов) изменены
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>↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский Roronoa__Zoro 2024-01-06 06:48:55 1
en4 Английский Roronoa__Zoro 2024-01-06 06:48:41 1
en3 Английский Roronoa__Zoro 2024-01-05 16:38:18 1
en2 Английский Roronoa__Zoro 2024-01-04 19:08:03 113
en1 Английский Roronoa__Zoro 2024-01-04 19:06:04 1405 Initial revision (published)