Problem D solution went into infinite loop on test case #115

Правка en2, от rohitranjan017, 2016-08-30 00:28:21

I am trying to implement Kosaraju for question 369 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

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 par[200005];

bool vis[200005],revis[200005],permvis[200005];

stack 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);

}

Теги 369, kosaraju

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский rohitranjan017 2016-08-30 14:43:48 997
en2 Английский rohitranjan017 2016-08-30 00:28:21 625
en1 Английский rohitranjan017 2016-08-30 00:26:14 1940 Initial revision (published)