11709 - Trust Groups

[charles1117]

I have a problem with 11709.
It seems to be a easy question -- finding out the number of sets where people in the set trust each other
But I am getting WA continuously.

Can anyone help to check my code?
Thanks really much!

Charles

Code: Select all

#include <iostream>
#include <map>
using namespace std;

map<string, int> People;
map<int, bool> m;
int trust[1001][1001];
int group[1001];

int main() {
   int P, T, ppl, ppl2;
   string temp, temp2;
   while (scanf("%d %d", &P, &T), P || T) {
      cin.get();
      memset(trust, 0, sizeof(trust));
      People.clear();
      m.clear();
      for (int x = 0; x < P; x++) {
         getline(cin, temp);
         People[temp] = x;
         group[x] = x;
      }
      for (int x = 0; x < T; x++) {
         getline(cin, temp);
         getline(cin, temp2);
         ppl = People[temp];
         ppl2 = People[temp2];
         trust[ppl][ppl2] = true;
         if (group[ppl2] != group[ppl] && trust[ppl2][ppl]) {
            for (int y = 0; y < P; y++)
               if (group[y] == group[ppl2] && y != ppl2)
                  group[y] = group[ppl];
            group[ppl2] = group[ppl];
         }
      }
      for (int x = 0; x < P; x++)
         m[group[x]] = true;
      printf("%d\n", (int)m.size());
   }
}


[shakil]

Why WA!!! Please give me some test case. Thanks.

Code: Select all

CUT


[robot]

Why WA!!! Please give me some test case. Thanks.

Code: Select all

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

struct TT
{
   char x[30];
};

TT nam[1009];
char temp[30];
long sam[1009][1009],A[1009][1009];
long n,m,i,j,visit[1009],ind[1009];
long p1,p2,count;

int cmp( const void *a, const void *b )
{
   TT *p = (TT *)a;
   TT *q = (TT *)b;

   return ( strcmp(p->x,q->x) );
}

long N(char h1[30])
{
long left,right,mid,h2;
left = 0;
right = n-1;
mid = (left+right)/2;
while(left<=right)
{
 h2 = strcmp(h1,nam[mid].x);
 if(h2==0)
 return mid;
 else if(h2>0)
 left = mid+1;
 else
 right = mid-1;
 mid = (left+right)/2;                 
}
return 0;     
}

int main()
{

while(1)
{
gets(temp);
sscanf(temp,"%ld %ld",&n,&m);   
if(n==0&&m==0)
break;   

for(i=0;i<n;i++)
{
gets(nam[i].x);
visit[i]=0;
ind[i]=0;
}

for(i=0;i<n;i++)
for(j=0;j<n;j++)
A[i][j]=0;

qsort(nam,n,sizeof(TT),cmp);

for(i=0;i<m;i++)
{
gets(temp);
p1 = N(temp);
gets(temp);               
p2 = N(temp);
if(A[p1][p2]==0)
{
 sam[p2][ind[p2]]=p1;
 A[p1][p2]=1;
 ind[p2]++;
 
 for(j=0;j<ind[p1];j++)
 if(A[sam[p1][j]][p2]==0)
 {
 A[sam[p1][j]][p2]==1;
 sam[p2][ind[p2]]=sam[p1][j];
 ind[p2]++;
 }
}               
}   

count=0;
for(i=0;i<n;i++)   
if(visit[i]==0)
{
visit[i]=1;
count++;
for(j=0;j<n;j++)
if(A[i][j]==1&&A[j][i]==1)
visit[j]=1;               
}

printf("%ld\n",count);

}   
return 0;   
}


Hi, Shakil
try this input
ur code cannot generate proper output
4 4
A, a
B, b
C, c
D, d
A, a
B, b
B, b
C, c
B, b
D, d
C, c
A, a
output: 2
ASU(Sust)

[robot]

I have a problem with 11709.
It seems to be a easy question -- finding out the number of sets where people in the set trust each other
But I am getting WA continuously.

Can anyone help to check my code?
Thanks really much!

Charles

Code: Select all

#include <iostream>
#include <map>
using namespace std;

map<string, int> People;
map<int, bool> m;
int trust[1001][1001];
int group[1001];

int main() {
   int P, T, ppl, ppl2;
   string temp, temp2;
   while (scanf("%d %d", &P, &T), P || T) {
      cin.get();
      memset(trust, 0, sizeof(trust));
      People.clear();
      m.clear();
      for (int x = 0; x < P; x++) {
         getline(cin, temp);
         People[temp] = x;
         group[x] = x;
      }
      for (int x = 0; x < T; x++) {
         getline(cin, temp);
         getline(cin, temp2);
         ppl = People[temp];
         ppl2 = People[temp2];
         trust[ppl][ppl2] = true;
         if (group[ppl2] != group[ppl] && trust[ppl2][ppl]) {
            for (int y = 0; y < P; y++)
               if (group[y] == group[ppl2] && y != ppl2)
                  group[y] = group[ppl];
            group[ppl2] = group[ppl];
         }
      }
      for (int x = 0; x < P; x++)
         m[group[x]] = true;
      printf("%d\n", (int)m.size());
   }
}


Hi , Charles
try this input
ur code fail for this input
4 4
A, a
B, b
C, c
D, d
A, a
B, b
B, b
C, c
B, b
D, d
C, c
A, a
output: 2
ASU(Sust)

[sreejond]

It seems to me the problem is finding the minimum number of cycles in the forest.
Is I'm right?
How to find minimum number of cycles in the forest...what is the algo????

Thnx in advance.

[helloneo]

It seems to me the problem is finding the minimum number of cycles in the forest.
Is I'm right?
How to find minimum number of cycles in the forest...what is the algo????

Thnx in advance.

I solved this problem with finding SCC..
There is a well known algorithm to find SCC using 2 DFSs..
I think it is called Tarjan's algorithm..

[shiam]

I have Tarjan's algo but still wa can I have some test cases.

Code: Select all

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iomanip>

/*** typedef ***/

#define MEMSET_INF 127
#define MEMSET_HALF_INF 63
#define stream istringstream
#define rep(i,n) for(__typeof(n) i=0; i<(n); i++)
#define repl(i,n) for(__typeof(n) i=1; i<=(n); i++)
#define FOR(i,a,b) for(__typeof(b) i=(a); i<=(b); i++)
#define INF (1<<30)
#define PI acos(-1.0)
#define pb push_back
#define ppb pop_back
#define all(x) x.begin(),x.end()
#define mem(x,y) memset(x,y,sizeof(x))
#define memsp(x) mem(x,MEMSET_INF)
#define memdp(x) mem(x,-1)
#define memca(x) mem(x,0)
#define eps 1e-9
#define pii pair<int,int>
#define pmp make_pair
#define ft first
#define sd second
#define pf printf
#define sf scanf
#define vi vector<int>
#define vpii vector<pii>
#define si set<int>
#define msi map<string , int >
#define mis map<int , string >
typedef long long i64;
typedef unsigned long long ui64;

/** function **/

#define SDi(x) sf("%d",&x)
#define SDl(x) sf("%lld",&x)
#define SDs(x) sf("%s",x)
#define SD2(x,y) sf("%d%d",&x,&y)
#define SD3(x,y,z) sf("%d%d%d",&x,&y,&z)

using namespace std;

#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
const i64 INF64 = (i64)1E18;

template<class T> inline T gcd(T a,T b) {if(a<0)return
gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
template<class T> inline T lcm(T a,T b) {if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}
template<class T> inline T sqr(T x){return x*x;}
template<class T> T power(T N,T P){ return (P==0)?  1: N*power(N,P-1); }
template<class T> bool inside(T a,T b,T c){ return (b>=a && b<=c);}


double _dist(double x1,double y1,double x2,double y2){return sqrt(sqr(x1-x2)+sqr(y1-y2));}
int distsq(int x1,int y1,int x2,int y2){return sqr(x1-x2)+sqr(y1-y2);}
i64 toInt64(string s){i64 r=0;istringstream sin(s);sin>>r;return r;}

double LOG(i64 N,i64 B){   return (log10l(N))/(log10l(B));   }
string itoa(long long a){if(a==0) return "0";string ret;for(long long i=a; i>0; i=i/10) ret.push_back((i%10)+48);reverse(ret.begin(),ret.end());return ret;}

vector< string > token( string a, string b )
{
    const char *q = a.c_str();while( count( b.begin(), b.end(), *q ) ) q++;vector< string >
   oot;while( *q ) {const char *e = q;while( *e && !count( b.begin(), b.end(),
   *e ) ) e++;oot.push_back( string( q, e ) );q = e;while( count( b.begin(),
   b.end(), *q ) ) q++;}return oot;
}
int isvowel(char s){s=tolower(s); if(s=='a' || s=='e' || s=='i' || s=='o' || s=='u')return 1; return 0;}
int isupper(char s) {if(s>='A' and s<='Z') return 1; return 0;}
template<class T> struct Fraction{T a,b;Fraction(T a=0,T b=1);string toString();};//NOTES:Fraction
template<class T> Fraction<T>::Fraction(T a,T b){T d=gcd(a,b);a/=d;b/=d;if (b<0) a=-a,b=-b;this->a=a;this->b=b;}
template<class T> string Fraction<T>::toString(){ostringstream sout;sout<<a<<"/"<<b;return sout.str();}
template<class T> Fraction<T> operator+(Fraction<T> p,Fraction<T> q){return Fraction<T>(p.a*q.b+q.a*p.b,p.b*q.b);}
template<class T> Fraction<T> operator-(Fraction<T> p,Fraction<T> q){return Fraction<T>(p.a*q.b-q.a*p.b,p.b*q.b);}
template<class T> Fraction<T> operator*(Fraction<T> p,Fraction<T> q){return Fraction<T>(p.a*q.a,p.b*q.b);}
template<class T> Fraction<T> operator/(Fraction<T> p,Fraction<T> q){return Fraction<T>(p.a*q.b,p.b*q.a);}

//bool operator < ( const node& p ) const {      return dist > p.dist;   }

/** Bitamsk **/

int SET(int N,int pos){   return N=N | (1<<pos);}
int RESET(int N,int pos){   return N= N & ~(1<<pos);}
int check(int N,int pos){   return (N & (1<<pos));}
int toggle(int N,int pos){if(check(N,pos))return N=RESET(N,pos);return N=SET(N,pos);}
void PRINTBIT(int N){   printf("("); for(int i=6;i>=1;i--)   {bool x=check(N,i);cout<<x;}   puts(")");}

const i64 INFFF=1e16;

#define N 1010
int n,gp;
msi m;
vi G[N];

int Stack[N], top;
int Index[N], Lowlink[N];
bool Onstack[N];
int Component[N];
int idx, components;


void tarjan(int u) {
   int v, i;
   Index[u] = Lowlink[u] = idx++;
   Stack[top++] = u;
   Onstack[u] = 1;
   for(i = 0; i < (int)G[u].size(); i++) {
      v = G[u][i];
      if(Index[v]==-1) {
         tarjan(v);
         Lowlink[u] = min(Lowlink[u], Lowlink[v]);
      }
      else if(Onstack[v]) Lowlink[u] = min(Lowlink[u], Index[v]);
   }
   if(Lowlink[u] == Index[u]) {
      components++;
      do {
         v = Stack[--top];
         Onstack[v] = 0;
      } while(u != v);
   }
}

int main()
{
    while(SD2(n,gp)&&n&&gp)
    {
        getchar();
        int id=1;
        char ch[200];
        rep(i,n)
        {
            gets(ch);
            string s(ch);
            m[s]=id++;
        }
        rep(i,gp)
        {
            gets(ch);
            string s1(ch);
            gets(ch);
            string s2(ch);
            int u = m[s1], v = m[s2];
            G[u].pb(v);
        }
        components = top = idx = 0;
        memdp(Index);
        memca(Onstack);
        memsp(Lowlink);

        for(int i = 1; i <= n; i++)
            if(Index[i]==-1)
                tarjan(i);

        m.clear();
        int i=n+2;
        while(i--) G[i].clear();

        pf("%d\n",components);
    }
    return 0;
}



Thanks in advance.