#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
using namespace std;
vector<int> a;
vector<int> req;
vector<int> deg;
int n;
vector<int> neigh;
vector<vector<int>> neigh2;
vector<set<int>> neigh3;
vector<int> visited;
vector<int> visited2;
queue<int> leefs;
queue<int> att;
int rst=0;
vector<vector<int>> compo;
vector<int> compoINDEX;
vector<int> topo;
void dfs(int x){
visited[x]=1;
if(!visited[neigh[x]]) dfs(neigh[x]);
topo.push_back(x);
}
void dfs2(int x){
if(visited[x]==2) return;
visited[x]=2;
compo.back().push_back(x);
compoINDEX[x]=sz(compo)-1;
for (auto u : neigh2[x])
{
dfs2(u);
}
}
void dfs3(int x){
visited[x]=true;
rst++;
if(visited[neigh[x]]||neigh[x]==x) return;
visited[neigh[x]]=true;
deg[neigh[neigh[x]]]--;
if(deg[neigh[neigh[x]]]==0&&neigh[x]!=neigh[neigh[x]]) leefs.push(neigh[neigh[x]]);
return;
}
void dfs4(int x){
visited[x]=true;
rst++;
if(visited[neigh[x]]||neigh[x]==x) return;
visited[neigh[x]]=true;
deg[neigh[neigh[x]]]--;
if(deg[neigh[neigh[x]]]==0&&neigh[x]!=neigh[neigh[x]]) leefs.push(neigh[neigh[x]]);
return;
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
neigh.resize(n);
neigh2.resize(n);
deg.resize(n);
compoINDEX.resize(n);
visited.resize(n);
map<string,int> mp;
int t=0;
for (int i = 0; i < n; i++)
{
string sa; string b; cin >> sa >> b;
if(mp.find(sa)==mp.end()){
//cerr << sa << " " << t<< "\n";
mp[sa]=t++;
}
if(mp.find(b)==mp.end()) {
//cerr << b << " " << t <<"\n";
mp[b]=t++;
}
neigh[mp[sa]]=mp[b];
neigh2[mp[b]].push_back(mp[sa]);
}
for (int i = 0; i < n; i++)
{
if(visited[i]==0) dfs(i);
}
for (int i = n-1; i >= 0; i--)
{
if(visited[topo[i]]==2) continue;
compo.push_back({});
dfs2(topo[i]);
}
neigh3.resize(sz(compo));
visited2.resize(n);
for (int i = 0; i < n; i++) visited[i]=false;
for (int i = 0; i < sz(compo); i++)
{
if(sz(compo[i])>2) {
for (int j = 0; j < sz(compo[i]); j++) visited2[compo[i][j]]=1;
}else if(sz(compo[i])==2) {
for (int j = 0; j < sz(compo[i]); j++) visited[compo[i][j]]=1;
}
}
for (int i = 0; i < n; i++) {
if(visited2[neigh[i]]==1&&visited2[i]!=1) visited2[i]=2;
deg[neigh[i]]++;
}
for (int i = 0; i < n; i++) {
if(deg[i]==0) leefs.push(i);
}
while(!leefs.empty())
{
int u=leefs.front(); leefs.pop();
if(visited2[u]>0||visited[u]) continue;
dfs3(u);
}
for (int i = 0; i < n; i++)
{
if(!visited[i]&&visited2[i]==2&&visited[neigh[i]]==0) {
visited[neigh[i]]=true;
visited[i]=true;
rst++;
}
else if(!visited[i]&&visited2[i]!=1) { visited[i]=true; rst++; }
}
for (int i = 0; i < n; i++) {
if(visited[i]) continue;
deg[neigh[i]]++;
}
for (int i = 0; i < n; i++) {
if(deg[i]==0) leefs.push(i);
}
while(!leefs.empty())
{
int u=leefs.front(); leefs.pop();
if(visited[u]) continue;
dfs4(u);
}
for (int i = 0; i < n; i++)
{
if(!visited[i]) dfs4(i);
}
if(n%2) cout << -1 << "\n";
else cout << rst << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |