I am trying to implement Kosaraju for question [369 D](http://mirror.codeforces.com/contest/711/problem/D) but i guess it goes into some into some infinite loop on test case #115. I am not able to figure out why is it so. Here is my code↵
↵
↵
#include<bits/stdc++.h>↵
#define up(j,k,i) for(i=j;i<k;i++)↵
#define down(j,k,i) for(i=j;i>k;i--)↵
#define M 1000000007↵
#define pp(n) printf("%lld\n",ll(n))↵
#define ps(n) printf("%lld ",ll(n))↵
#define pd(x,y) printf("%lld %lld\n",ll(x),ll(y))↵
#define is(n) scanf("%lld",&n)↵
#define Max(x,y) max(ll(x),ll(y))↵
#define Min(x,y) min(ll(x),ll(y))↵
#define inf LLONG_MAX↵
#define id(n,m) scanf("%lld%lld",&n,&m)↵
#define it(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)↵
#define ss(s) scanf("%s",s)↵
#define cool 0↵
#define pb push_back↵
#define mp make_pair↵
#define F first↵
#define S second↵
#define pll pair<ll,ll> ↵
#define db cout<<"######\n"↵
#define null(a) memset(a,0,sizeof(a))↵
#define neg(a) memset(a,255,sizeof(a))↵
typedef long double ld;↵
typedef long long int ll;↵
using namespace std;↵
ll i,j,k,z,t,n,m,sum,ans,x,y,maxm=0,minm=inf;↵
typedef long long int ll;↵
using namespace std;↵
ll i,j,k,z,t,n,m,sum,ans,x,y,maxm=0,minm=inf;↵
↵
map<ll,ll> child;↵
↵
vector<ll> par[200005];↵
↵
bool vis[200005],revis[200005],permvis[200005];↵
↵
stack<ll> s;↵
↵
ll fact[400005];↵
↵
void dfs(ll x)↵
{↵
↵
if(vis[x]) return;↵
↵
vis[x]=1;↵
↵
dfs(child[x]);↵
↵
s.push(x);↵
}↵
↵
void rev_dfs(ll x,ll cnt)↵
{↵
↵
permvis[x]=1;↵
↵
revis[x]=1;↵
↵
for(auto c:par[x])↵
↵
if(revis[c]!=1)↵
rev_dfs(c,cnt+1);↵
↵
else if(revis[c])↵
z=1,ans=cnt+1;↵
↵
revis[x]=0;↵
↵
}↵
int main()↵
{↵
fact[0]=1;↵
sum=1;↵
↵
is(n);↵
↵
up(1,n+1,i)↵
fact[i]=fact[i-1]*2%M;↵
↵
up(1,n+1,i)↵
{↵
is(x);↵
child[i]=x;↵
par[x].pb(i);↵
}↵
↵
up(1,n+1,i)↵
if(!vis[i])↵
dfs(i);↵
↵
while(!s.empty())↵
{↵
ans=0; z=0;↵
↵
x=s.top();↵
s.pop();↵
↵
if(permvis[x]) ↵
continue;↵
↵
rev_dfs(x,0);↵
↵
if(z)↵
sum=sum*(fact[ans]-2)%M,y+=ans;↵
↵
}↵
↵
sum=sum*(fact[n-y])%M;↵
↵
pp((sum+M)%M);↵
↵
}↵
↵
↵
#include<bits/stdc++.h>↵
#define up(j,k,i) for(i=j;i<k;i++)↵
#define down(j,k,i) for(i=j;i>k;i--)↵
#define M 1000000007↵
#define ps(n) printf("%lld ",ll(n))↵
#define pd(x,y) printf("%lld %lld\n",ll(x),ll(y))↵
#define is(n) scanf("%lld",&n)↵
#define Max(x,y) max(ll(x),ll(y))↵
#define Min(x,y) min(ll(x),ll(y))↵
#define inf LLONG_MAX↵
#define id(n,m) scanf("%lld%lld",&n,&m)↵
#define it(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)↵
#define ss(s) scanf("%s",s)↵
#define cool 0↵
#define pb push_back↵
#define mp make_pair↵
#define F first↵
#define S second↵
#define pll pair<ll,ll> ↵
#define db cout<<"######\n"↵
#define null(a) memset(a,0,sizeof(a))↵
#define neg(a) memset(a,255,sizeof(a))↵
typedef long double ld;↵
typedef long long int ll;↵
using namespace std;↵
ll i,j,k,z,t,n,m,sum,ans,x,y,maxm=0,minm=inf;
typedef long long int ll;↵
using namespace std;↵
ll i,j,k,z,t,n,m,sum,ans,x,y,maxm=0,minm=inf;↵
↵
map<ll,ll> child;↵
↵
vector<ll> par[200005];↵
↵
bool vis[200005],revis[200005],permvis[200005];↵
↵
stack<ll> s;↵
↵
ll fact[400005];↵
↵
void dfs(ll x)↵
{↵
↵
if(vis[x]) return;↵
↵
vis[x]=1;↵
↵
dfs(child[x]);↵
↵
s.push(x);↵
}↵
↵
void rev_dfs(ll x,ll cnt)↵
{↵
↵
permvis[x]=1;↵
↵
revis[x]=1;↵
↵
for(auto c:par[x])↵
↵
if(revis[c]!=1)↵
rev_dfs(c,cnt+1);↵
↵
else if(revis[c])↵
z=1,ans=cnt+1;↵
↵
revis[x]=0;↵
↵
}↵
int main()↵
{↵
fact[0]=1;↵
sum=1;↵
↵
is(n);↵
↵
up(1,n+1,i)↵
fact[i]=fact[i-1]*2%M;↵
↵
up(1,n+1,i)↵
{↵
is(x);↵
child[i]=x;↵
par[x].pb(i);↵
}↵
↵
up(1,n+1,i)↵
if(!vis[i])↵
dfs(i);↵
↵
while(!s.empty())↵
{↵
ans=0; z=0;↵
↵
x=s.top();↵
s.pop();↵
↵
if(permvis[x]) ↵
continue;↵
↵
rev_dfs(x,0);↵
↵
if(z)↵
sum=sum*(fact[ans]-2)%M,y+=ans;↵
↵
}↵
↵
sum=sum*(fact[n-y])%M;↵
↵
pp((sum+M)%M);↵
↵
}↵
