11838 - Come and Go

[TISARKER]

I used tarjan's algorithm. I am getting wrong answer. I spent a lot of time to this but did not get the reason. Can any one help me to fix my error.

Here is my code:

Code: Select all

Cut After Accepted

[sitz]

Well, You can simply use Floyd-Warshall to get AC in this question, that will suffice for it

Regards,
SITZ

[TISARKER]

Thanks Got accepted now. I did a silly pen mistake.

[asif_iut]

Code: Select all

#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<cctype>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<map>
#include<sstream>
#include<vector>
using namespace std;

typedef vector<int> vi;
typedef vector< vi > vii;
typedef map<int,int> mii;
typedef map<string,int> msi;
typedef map<int,string> mis;


#define pb push_back
#define MAX 2005

int path[ MAX ][ MAX ];
bool visit[ MAX ];
int ind[ MAX ];
int N,M;
int caseId;
int low[ MAX ];
int c ;
stack< int > node;
int ans;

int mini( int a, int b ){
	return ( ( a <= b ) ? a : b ) ;
}

void tarjan( int x ){
	ind[ x ] = c;
	low[ x ] = c;
	c ++;
	node.push( x );
	for( int i = 1; i <= N; i ++ ){
		if( path[ x ][ i ] == caseId ) {
			if( ind[ i ] == -1 ){
				tarjan( i );
				low[ x ] = mini( low[ x ], low[ i ] );
			}

			else low[ x ] = mini( low[ x ], low[ i ] );
		}
	}

	if( low[ x ] == ind[ x ] ) {
		
		ans ++;
			
	}

}

int main(){
//	freopen("a.txt", "r", stdin);
	caseId = 0;
	int i,j,a,b,v;
	while( scanf("%d %d", &N, &M) == 2 ){
		if( N == 0 && M == 0 ) break;
		++caseId;
		ans = 0;
		memset( ind, -1, sizeof( ind ) );
		while( !node.empty() ) node.pop();
		c = 0;
		for( i = 0; i < M; i ++ ){
			scanf("%d %d %d", &a, &b, &v);
			if( v == 1 ) path[ a ][ b ] = caseId;
			else path[ a ][ b ] = path[ b ][ a ] = caseId;
		}

		for( i = 1; i <= N; i ++ ){
			if( ind[ i ] == -1 ) 
				tarjan( i );
		}

		if( ans == 1 ) printf("%d\n",ans);
		else printf("%d\n",0);
	}
	return 0;
}

this is the first SSC problem i am trying to solve but i am getting WA...is there any problem in the code ??..thanks in advance

[Jehad Uddin]

your implementation of tarjans algorithm is not correct.
see http://en.wikipedia.org/wiki/Tarjan's_s ... _algorithm
there are some pop operations you are missing

Code: Select all

int pp;

void tarjan( int x ){
   ind[ x ] = c;
   low[ x ] = c;
   c ++;
   node.push( x );
   for( int i = 1; i <= N; i ++ ){
      if( path[ x ][ i ] == caseId ) {
         if( ind[ i ] == -1 ){
            tarjan( i );
            low[ x ] = min( low[ x ], low[ i ] );
         }

         else low[ x ] = min( low[ x ], low[ i ] );
      }
   }

   if( low[ x ] == ind[ x ] ) {

      ans ++;
     pp= node.top();
     node.pop();
     while(pp!=x) pp=node.top(),node.pop();
   }


}

and you can change this part 
tarjan(1);

      for( i = 2; i <= N; i ++ ){
         if( ind[ i ] == -1 ) ans=-2;
            //tarjan( i ); no need to call tarjan again and again
      }

      if( ans == 1 ) printf("%d\n",ans);
      else printf("%d\n",0);

[MRH]

This problem also sloved by simple dfs or mst

[CyberPunk]

I used Tarjan's SCC Algorithm to find the number of SCC in the given graph. The answer is 1 if number of SCC is 1, else the answer is 0. Now this gives WA and I can't find why. So please help me. This is the first time I'm doing SCC.

Code: Select all

#include <bits/stdc++.h>

using namespace std;

#ifdef __GNUC__
typedef long long LL;typedef unsigned long long LLU;
#else
typedef __int64 LL;  typedef unsigned __int64 LLU;
#endif

typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef pair<LL,LL> PLL;
typedef vector<int> VI;
typedef vector<double> VD;
typedef vector<LL> VLL;
typedef vector<string> VS;
typedef vector<PII> VPII;
typedef vector<PDD> VPDD;
typedef vector<PLL> VPLL;
typedef map<string,int> MSI;
typedef map<int,int> MII;
typedef map<PII,int> MPI;

#define MOD 1000000009
#define PI 3.14159265358979323846264338327950
#define EPS 1e-9
#define INF 2000000000

#define REP(x,a,b) for(int x = int(a); x<=int(b); x++)
#define REPi(n) for(int i = 0; i<n; i++)
#define REPj(n) for(int j = 0; j<n; j++)

#define INi1(x) scanf("%d", &x)
#define INi2(x,y) scanf("%d %d", &x, &y)
#define INi3(x,y,z) scanf("%d %d %d", &x, &y, &z)
#define INll1(x) scanf("%lld", &x)
#define INll2(x,y) scanf("%lld %lld", &x, &y)
#define INll3(x,y,z) scanf("%lld %lld %lld", &x, &y, &z)
#define INd1(x) scanf("%lf", &x)
#define INd2(x,y) scanf("%lf %lf", &x, &y)
#define INd3(x,y,z) scanf("%lf %lf %lf", &x, &y, &z)
#define OUTi(x) printf("%d\n",x)
#define OUTll(x) printf("%lld\n",x)
#define OUTd(x) printf("%lf\n",x)
#define NL puts("");
#define DEB(str) cout<<str<<endl;
#define DEB1(x) cout<<x<<endl
#define DEB2(x,y) cout<<x<<' '<<y<<endl
#define DEB3(x,y,z) cout<<x<<' '<<y<<' '<<z<<endl

#define MEM(x,y) memset(x,y,sizeof(x))
#define SORT(x) sort(x.begin(),x.end())
#define POP(x) __builtin_popcount(x)
#define GCD(x,y) __gcd(x,y)
#define LCM(x,y) ( (x*y)/__gcd(x,y) )

#define PB push_back
#define PoB pop_back
#define PF push_front
#define PoF pop_front
#define MP make_pair
#define P1 first
#define P2 second

#define IN(f) freopen(f, "r", stdin)
#define OUT(f) freopen(f, "w", stdout)

template<class T> inline bool Equal(T x, T y) { return fabs(x-y) < EPS;}
template<class T> inline T Exp( T x, T y) { if(y==0) return 1; if(y==1) return x; T ans=Exp(x,T(LL(y)/2)); return ans*ans*Exp(x,T(LL(y)%2));}
template<class T> inline T Mod(T n, T m) { return (n%m + m)%m;}

template<class T> inline T Set(T N,T pos) { return N | (1<<pos);}
template<class T> inline T Reset(T N,T pos) { return N & ~(1<<pos);}
template<class T> inline bool Check(T N, T pos) { return N & (1<<pos);}

#define MAX 2000

vector<int> adj[MAX+5];
int id[MAX+5], lowlink[MAX+5];
bool inStack[MAX+5];
stack<int> st;
int K, SCC, V;

void strongConnect(int v)
{
    id[v] = K;
    lowlink[v] = K++;
    st.push(v);
    inStack[v] = true;

    int w;

    while(!adj[v].empty())
    {
        w = adj[v].back();
        if(!id[w])
        {
            strongConnect(w);
            lowlink[v] = min( lowlink[v], lowlink[w]);
        }
        else if(inStack[v])
        {
            lowlink[v] = min( lowlink[v], id[w]);
        }
        adj[v].pop_back();
    }

    if(id[v]==lowlink[v])
    {
        do{
            w = st.top();
            inStack[w] = false;
            st.pop();
        }while(w!=v);

        SCC++;
    }
}

void tarjan(void)
{
    for(int i = 1; i<=V; i++) id[i] = 0;
    SCC = 0, K = 1;

    for(int i = 1; i<=V; i++) if(!id[i]) strongConnect(i);

    if(SCC == 1) puts("1");
    else puts("0");
}


int main()
{
    int E, u, v, p;
    while(scanf("%d %d", &V, &E) && (V|E))
    {
        while(E--)
        {
            scanf("%d %d %d", &u, &v, &p);
            adj[u].push_back(v);
            if(p==2) adj[v].push_back(u);
        }

        tarjan();
    }


    return 0;
}

[brianfry713]

This problem can be solved by simple DFS.