【No.019】「 SRM 691 div1 easy 」

コンテスト中に書いたコードがいろいろと無駄なことをしていたので、書き直しました。（かなり短くなりました。）

 

 

#include <bits/stdc++.h>
using namespace std;

class Sunnygraphs {
public:
map<int,bool> mp;
void func(int &cnt,int p,vector<int> &a){
while(!mp[p])mp[p]=true,cnt++,p=a[p];
}

long long count(vector <int> a) {
int n=a.size();
int ac=0,bc=0,cc=0,dc=0;
mp.clear();
func(ac,0,a);
func(bc,1,a);
mp.clear();
func(cc,1,a);
func(dc,0,a);
int C=n-ac-bc;
long long ans=(1LL<<n);
ans-=((1LL<<bc)-1LL)*(1LL<<C);
ans-=((1LL<<dc)-1LL)*(1LL<<C);
if(ac==dc)ans-=(1LL<<C);
return ans;
}
};

変数acは、エッジを向有としたとき（ i 番目のノードから a[ i ] 番目のノードに向かってエッジを張る）に、0のノードから到達可能なノードの個数です。

変数bcは、0のノードからは到達可能だけれど、0のノードからの到達が不可能なノードの個数です。

似たような感じで、ccは1から到達可能、dcは0から到達で1から到達不可能なノードの個数です。

 acとdcが等しいときは、0のノードと1のノードが異なる連結成分に存在していることになります。